二叉堆
特性
- 最大堆的堆顶是整个堆中的最大元素
- 最小堆的堆顶是整个堆中的最小元素
每次删除旧堆顶，调整后的新堆顶都是大小仅次于旧堆顶的节点。
只要反复删除堆顶，反复调整二叉堆，所得到的集合就会成为一个有序集合。
简述
堆排序算法步骤：
- 把无序数组构建成二叉堆。需要从小到大排序，就构建成最大堆。需要从大到小排序，就构建成最小堆。
- 循环删除堆顶元素，替换到二叉堆的末尾，调整堆，产生新的堆顶。
复杂度
| 名称 | 最好 | 平均 | 最差 | 空间 | 稳定性 |
| 堆排序 | nlog(n) | nlog(n) | nlog(n) | 1 | 否 |
实现
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
//上浮调整 void upAdjust(int array[], int length) { int childIndex = length - 1; int parentIndex = (childIndex - 1) / 2; //temp保存插入的叶子节点值，用于最后的赋值 int temp = array[childIndex]; while (childIndex > 0 && temp < array[parentIndex]) { //无须真正交换，单向赋值即可 array[childIndex] = array[parentIndex]; childIndex = parentIndex; parentIndex = (parentIndex - 1) / 2; } array[childIndex] = temp; } //下沉调整 void downAdjust(int array[],int parentIndex,int length) { //temp保存父节点的值，用于最后赋值 int temp = array[parentIndex]; int childIndex = 2 * parentIndex + 1; while(childIndex < length) { //如果有右孩子，且右孩子的值大于左孩子的值，则定位到右孩子 if(childIndex + 1 < length && array[childIndex+1] > array[childIndex]) childIndex++; //如果父节点大于任何一个孩子的值，则直接跳出 if(temp >= array[childIndex]) break; //无需真正交换，单向赋值即可 array[parentIndex] = array[childIndex]; parentIndex = childIndex; childIndex = 2 * childIndex + 1; } array[parentIndex] = temp; } //堆排序（升序：最大堆） void HeapSort(int array[],int length) { //把无序数组构建成最大堆 for(int i = (length-2)/2;i >= 0; i--) downAdjust(array,i,length); //循环删除堆顶元素，移到集合尾部，调整堆，新产生堆顶 for(int i = length - 1; i > 0; i--) { //最后一个元素和第一个元素交换 int temp = array[i]; array[i] = array[0]; array[0] = temp; //"下沉"调整 downAdjust(array,0,i); } } |
算法导论
堆排序思想：假设对数组A[p...r]排序：首先将数组构建成一个最大堆（或者最小堆，这里的实现采用最大堆）。然后第一个元素就是堆中最大的元素。
将第一个元素与最后一个元素交换，同时堆的规模缩减1，再将堆维持最大堆性质。不断循环最后得到一个排序好的序列
- 时间复杂度 O(nlogn)
- 原地排序
堆排序有两个重要操作：
- heapify(index)操作：维持以index为根节点的子堆的性质。它比较index与其左右子节点的值，选取其最大的那个提升到index节点上。同时递归向下。具体见_heapify()方法说明
- setupHeap()操作： 建堆操作。它从堆的最低层向上层反复调用heapify操作进行建堆。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
template<typename Iterator,typename CompareType=std::less<typename std::iterator_traits<Iterator>::value_type>> class Sort_Heap { public: typedef typename std::iterator_traits<Iterator>::value_type T; /*!< 迭代器指向对象的值类型*/ //!operator() /*! * \param from : 待排序序列的起始迭代器（也可以是指向数组中某元素的指针） * \param size: 待排序序列的长度 * \param compare: 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less<T> * \return void * * 首先调用 _setupHeap()建堆。然后再反复抽取最大值到堆尾部，然后维持堆的性质。 * * - 时间复杂度 O(nlogn) * - 原地排序 */ void operator () (const Iterator from, std::size_t size,CompareType compare=CompareType()) { _from=from; _size=size; _setupHeap(compare); while(_size>0) { std::swap(*_from,*(_from+_size-1)); _size--; _heapify(0,compare); } } protected: //!_setupHeap:建堆 /*! * \param compare: 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less<T> * \return void * * 从后一半的元素开始依次向前调用heapify操作（根据最大堆性质，除了最底层它是完全充满的） * * - 时间复杂度 O(nlogn) * - 原地操作 */ void _setupHeap(CompareType compare=CompareType()) { if(_size<=1) return; int index=(_size-1)/2; while(index>=0) { _heapify(index,compare); index--; } } //!_heapify：维持堆性质 /*! * \param elementIndex : 要维持以该节点为根节点的子堆的堆性质 * \param compare: 一个可调用对象，可用于比较两个对象的小于比较，默认为std::less<T> * \return void * * 首先调用比较该节点与左右子节点的最大值。如果最大值为它本身，则维持了性质，返回；如果最大值不是它本身，那么必然为左、右子节点之一。 * 将该最大节点（假设为左子节点）交换到根节点，然后以左子节点递归调用heapify操作 * * - 时间复杂度 O(n) * - 原地操作 */ void _heapify(std::size_t elementIndex,CompareType compare=CompareType()) { if(elementIndex>=_size) return; auto maxIndex=elementIndex; bool left_valid=true; bool right_valid=true; auto leftIndex=_lchildIndex(elementIndex,left_valid); auto rightIndex=_rchildIndex(elementIndex,right_valid); if(left_valid) { if( compare(*(_from+maxIndex),*(_from+leftIndex))) maxIndex=leftIndex; } if(right_valid) { if( compare(*(_from+maxIndex),*(_from+rightIndex))) maxIndex=rightIndex; } if(maxIndex!=elementIndex) { std::swap(*(_from+elementIndex),*(_from+maxIndex)); _heapify(maxIndex,compare); } } //!_parentIndex:返回一个节点的父节点位置 /*! * \param elementIndex : 子节点位置 * \param valid: 一个bool&值，用于返回，指示父节点是否有效 * \return 父节点位置(std::size_t) * * 根据最大堆的性质，一个子节点elementIndex的父节点是它的位置(elementIndex-1)/2。 * * - 超出堆大小的节点，其父节点无效 * */ std::size_t _parentIndex(std::size_t elementIndex,bool& valid) { if(elementIndex>=_size) { valid=false; //无效结果 return 0; } valid=true; //有效结果 if (elementIndex ==0) return 0; //根节点的父节点是自己 else return (elementIndex-1)>>1; } //!_lchildIndex:返回一个节点的左子节点位置 /*! * \param elementIndex : 节点位置 * \param valid: 一个bool&值，用于返回，指示子节点是否有效 * \return 左子节点位置(std::size_t) * * 根据最大堆的性质，一个节点elementIndex的左子节点是它的位置(elementIndex/2)+1 * * - 当最大堆大小为0、1时，它没有左子节点，左子节点无效 * - 当左子节点超过堆大小时，它无效 * */ std::size_t _lchildIndex(std::size_t elementIndex,bool& valid) { if(_size<2) { valid=false; //数组元素太少无效结果 return 0; } if( elementIndex>((_size-2)>>1) ) { valid=false;//超出范围，无效 return 0; } valid=true; return (elementIndex<<1)+1; } //!_rchildIndex:返回一个节点的右子节点位置 /*! * \param elementIndex : 节点位置 * \param valid: 一个bool&值，用于返回，指示子节点是否有效 * \return 右子节点位置(std::size_t) * * 根据最大堆的性质，一个节点elementIndex的右子节点是它的位置(elementIndex/2)+2 * * - 当最大堆大小为0、、1、2时，它没有右子节点，右子节点无效 * - 当右子节点超过堆大小时，它无效 * */ std::size_t _rchildIndex(std::size_t elementIndex,bool& valid) { if(_size<3) { valid=false; //数组元素太少无效结果 return 0; } if( elementIndex>((_size-3)>>1) ) { valid=false;//超出范围，无效 return 0; } valid=true; return (elementIndex<<1)+2; } private: Iterator _from;/*!< 堆根节点位置*/ std::size_t _size;/*!< 堆大小*/ }; |
本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！
你可能也喜欢
- ♥ 匹配_Rabin_karp匹配算法10/15
- ♥ 数据结构_二叉树节点10/16
- ♥ 匹配_朴素字符串匹配算法10/14
- ♥ 排序_归并排序09/04
- ♥ 匹配_KMP模式匹配算法：二10/09
- ♥ 查找_顺序查找05/09
热评文章
- 排序_快速排序 0
- 动态规划相关 0
- 数据结构_最小优先级队列 0
- 排序_冒泡排序 0
- 一些变量值交换的方法 0
- 匹配_KMP模式匹配算法：二 0