最大堆(创建、删除、插入和堆排序)图文详解 | 您所在的位置:网站首页 › procreat堆怎么取消 › 最大堆(创建、删除、插入和堆排序)图文详解 |
原文地址 我有一个不成熟的建议:老老实实花1个小时把这篇文章仔细看完,关于堆的各种操作一目了然了。 关于最大堆什么是最大堆和最小堆?最大(小)堆是指在树中,存在一个结点而且该结点有儿子结点,该结点的data域值都不小于(大于)其儿子结点的data域值,并且它是一个完全二叉树(不是满二叉树)。注意区分选择树,因为选择树(selection tree)概念和最小堆有些类似,他们都有一个特点是“树中的根结点都表示树中的最小元素结点”。同理最大堆的根结点是树中元素最大的。那么来看具体的看一下它长什么样?(最小堆这里省略)
那么我们在做最大堆的抽象数据类型(ADT)时就需要考虑三个操作: (1)、创建一个最大堆; (2)、最大堆的插入操作; (3)、最大堆的删除操作; 最大堆ADT如下: struct Max_Heap { object: 由多个元素组成的完全二叉树,其每个结点都不小于该结点的子结点关键字值 functions: 其中heap∈Max_Heap,n,max_size∈int,Element为堆中的元素类型,item∈ Element Max_Heap createHeap(max_size) := 创建一个总容量不大于max_size的空堆 void max_heap_insert(heap, item ,n) := 插入一个元素到heap中 Element max_heap_delete(heap,n) := if(heap不为空) {return 被删除的元素 }else{return NULL} } ///其中:=符号组读作“定义为” 最大堆内存表现形式我们只是简单的定义了最大堆的ADT,为了能够用代码实现它就必须要考虑最大堆的内存表现形式。从最大堆的定义中,我们知道不管是对最大堆做插入还是删除操作,我们必须要保证插入或者删除完成之后,该二叉树仍然是一个完全二叉树。基于此,我们就必须要去操作某一个结点的父结点。 第一种方式,我们使用链表的方式来实现,那么我们需要添加一个额外的指针来指向该结点的父结点。此时就包括了左子结点指针、右子结点指针和父结点指针,那么空链的数目有可能是很大的,比如叶子结点的左右子结点指针和根结点的父结点指针,所以不选择这种实现方式(关于用链表实现一般二叉树时处理左右子结点指针的问题在线索二叉树中有提及)。 第二种方式,使用数组实现,在二叉树进行遍历的方法分为:先序遍历、中序遍历、后序遍历和层序遍历。我们可以通过层序遍历的方式将二叉树结点存储在数组中,由于最大堆是完全二叉树不会存在数组的空间浪费。那么来看看层序遍历是怎么做的?对下图的最大堆进行层序遍历:
下面来看看最大堆的插入、删除和创建这三个最基本的操作。 最大堆的插入最大堆的插入操作可以简单看成是“结点上浮”。当我们在向最大堆中插入一个结点我们必须满足完全二叉树的标准,那么被插入结点的位置的是固定的。而且要满足父结点关键字值不小于子结点关键字值,那么我们就需要去移动父结点和子结点的相互位置关系。具体的位置变化,可以看看下面我画的一个简单的图。 void insert_max_heap(element item ,int *n){ if(HEAP_FULL(*n)){ return; } int i = ++(*n); for(;(i != 1) && (item.key > heap[i/2].key);i = i / 2){/// i ≠ 1是因为数组的第一个元素并没有保存堆结点 heap[i] = heap[i/2];/// 这里其实和递归操作类似,就是去找父结点 } heap[i] = item; }
最大堆的删除操作,总是从堆的根结点删除元素。同样根元素被删除之后为了能够保证该树还是一个完全二叉树,我们需要来移动完全二叉树的最后一个结点,让其继续符合完全二叉树的定义,从这里可以看作是最大堆最后一个结点的下沉(也就是下文提到的结点1)操作。例如在下面的最大堆中执行删除操作:
对上面三步图示如下:
同最大堆的插入操作类似,同样包含n个元素的最大堆,其高度为:log2(n+1),其时间复杂度为:O(log2(n))。 总结:由此可以看出,在已经确定的最大堆中做删除操作,被删除的元素是固定的,需要被移动的结点也是固定的,这里我说的被移动的元素是指最初的移动,即最大堆的最后一个元素。移动方式为从最大的结点开始比较。 最大堆的创建为什么要把最大堆的创建放在最后来讲?因为在堆的创建过程中,有两个方法。会分别用到最大堆的插入和最大堆的删除原理。创建最大堆有两种方法: (1)、先创建一个空堆,然后根据元素一个一个去插入结点。由于插入操作的时间复杂度为O(log2(n)),那么n个元素插入进去,总的时间复杂度为O(n * log2(n))。 (2)、将这n个元素先顺序放入一个二叉树中形成一个完全二叉树,然后来调整各个结点的位置来满足最大堆的特性。 现在我们就来试一试第二种方法来创建一个最大堆:假如我们有12个元素分别为: {79,66,43,83,30,87,38,55,91,72,49,9}将上诉15个数字放入一个二叉树中,确切地说是放入一个完全二叉树中,如下: 在做最大堆的创建具体步骤中,我们会用到最大堆删除操作中结点位置互换的原理,即关键字值较小的结点会做下沉操作。 1)、就如同上面所说找到二叉树中倒数第一个非叶子结点87,然后看以该非叶子结点为根结点的子树。查看该子树是否满足最大堆要求,很明显目前该子树满足最大堆,所以我们不需要移动结点。该子树最大移动次数为1。![]() ![]() ![]() ![]() ![]() 代码实现 void create_max_heap(void){ int total = (*heap).key; /// 求倒数第一个非叶子结点 int child = 2,parent = 1; for (int node = total/2; node>0; node--) { parent = node; child = 2*node; int max_node = 2*node+1; element temp = *(heap+parent); for (; child child++; } if (temp.key > (*(heap+child)).key) { break; } *(heap+parent) = *(heap+child); parent = child; } *(heap+parent) = temp; } } /** * * @param heap 最大堆; * @param items 输入的数据源 * @return 1成功,0失败 */ int create_binary_tree(element *heap,int items[MAX_ELEMENTS]){ int total; if (!items) { return 0; } element *temp = heap; heap++; for (total = 1; *items;total++,(heap)++,items = items + 1) { element ele = {*items}; element temp_key = {total}; *temp = temp_key; *heap = ele; } return 1; } ///函数调用 int items[MAX_ELEMENTS] = {79,66,43,83,30,87,38,55,91,72,49,9}; element *position = heap; create_binary_tree(position, items); for (int i = 0; (*(heap+i)).key > 0; i++) { printf("binary tree element is %d\n",(*(heap + i)).key); } create_max_heap(); for (int i = 0; (*(heap+i)).key > 0; i++) { printf("heap element is %d\n",(*(heap + i)).key); }上诉代码在我机器上能够成功的构建一个最大堆。由于该完全二叉树存在n个元素,那么他的高度为:log2(n+1),这就说明代码中的for循环会执行O(log2(n))次。因此其我理解的平均运行时间为:O(log2(n))。而其上界为当该二叉树为满二叉树时其时间复杂度为O((n)。 堆排序堆排序要比空间复杂度为O(n)的归并排序要慢一些,但是要比空间复杂度为O(1)的归并排序要快! 通过上面最大堆创建一节中我们能够创建一个最大堆。出于该最大堆太大,我将其进行缩小以便进行画图演示。
很明显这是一个正确的从小到大的顺序。 编码实现这里需要对上面的代码进行一些修改!因为在排序中,我们的第0个元素是不用去放一个哨兵的,我们的元素从原来的第一个位置改为从第0个位置开始放置元素。 void __swap(element *lhs,element *rhs){ element temp = *lhs; *lhs = *rhs; *rhs = temp; } int create_binarytree(element *heap, int items[MAX_SIZE], int n){ if (n items[i]}; *heap = value; } return 1; } void adapt_maxheap(element *heap ,int node ,int n){ int parent = node - 1 parent = 2 * child + 1 int max_node = max_node = 2*parent+2 child++; } if ((heap + child)->key for (int node = n/2; node > 0; node--) { adapt_maxheap(heap, node, n); } return 1; } void heap_sort(element *heap ,int n){ ///创建一个最大堆 create_maxheap(heap, n); ///进行排序过程 int i = n - 1; while (i >= 0) { __swap(heap+0, heap + i);/// 将第一个和最后一个进行交换 adapt_maxheap(heap, 0, i--);///将总的元素个数减一,适配成最大堆,这里只需要对首元素进行最大堆的操作 } }调用: /// 堆排序 int n = 7; int items[7] = {87,79,38,83,72,43,91}; element heap[7]; create_binarytree(heap, items, n); heap_sort(heap, n);///38,43,72,79,83,87,91在实现堆排序时最需要注意的就是当没有哨兵之后,父结点和左右孩子结点之间的关系发生了变化: parent = 2 * child + 1;///左孩子 parent = 2 * child + 2;///右孩子关于对排序相关的知识点已经整理完了。其时间复杂度和归并排序的时间时间复杂度是一样的O(N*LogN)。 结束语当我们在做和完全二叉树有关的操作时,对于完全二叉树采用顺序存储表示,需要记住对于任意一个下标为i(1 ≤ i ≤ n)的结点:父结点为:i / 2(i ≠ 1),若i = 1,则i是根节点。左子结点:2i(2i ≤ n), 若不满足则无左子结点。右子结点:2i + 1(2i + 1 ≤ n),若不满足则无右子结点。 关于最大堆的相关操作(插入、删除、创建和排序)已经一一学习完毕。这些操作中,删除、创建和排序思想非常类似,都是操作结点下沉。而插入操作相反,类似上浮的操作! |
CopyRight 2018-2019 实验室设备网 版权所有 |