堆和堆排序
文章目录
堆的概念和特性
堆(准确说是其中的二叉堆)有两种表达方式:二叉树或者数组
- 二叉树,树的每一层都是填满的,最后一层可能除外,但也是从左往右尽量填充。

- 数组,对应二叉树,第i个元素的父亲是 floor(i/2),左孩子是 2i,右孩子是2i+1。1
第i个元素的父亲是 floor((i-1)/2),左孩子是 2i+1,右孩子是2i+2。2
上面的树对应的数组是 [100, 19, 36, 17, 3, 25, 1, 2, 7]
最大堆(大顶堆)
堆中任意一个节点,都大于等于它的孩子。也就是说堆(树)中的任意一颗子树的最大值都在这棵树的根。
建立大顶堆
保持堆的性质 MAX-HEAPIFY
MAX-HEAPIFY是对大顶堆进行操作的最重要的子程序。其输入是一个数组A和下标i。当MAX-HEAPIFY被调用的时候,假定LEFT(i)和RIGHT(i)为根的两个子树都是大顶堆,但是A[i]可能小于其子女。MAX-HEAPIFY的作用就是使得A[i]下降,使得以i为根的子树称为大顶堆。
/* 保持堆性质
* 1. 找到i、LEFT(i)和RIGHT(i)三个位置中最大的一个,将位置记录到largest中;
* 2.1. 如果largest和i一样,说明以i为根的子树已经是大顶堆,程序结束。
* 2.2. 如果largest和i不一样,交换对应的值;
* 3. 由于largest位置的值变化,所以需要对largest为根的树调用heapify。
*/
void heapify(vector<int>& aList, int i) {
auto left = i * 2 + 1;
auto right = left + 1;
auto largest = i;
if (left < aList.size() && aList[left] > aList[largest]){
largest = left;
}
if (right < aList.size() && aList[right] > aList[largest]){
largest = right;
}
if (largest != i) {
auto tmp = aList[i];
aList[i] = aList[largest];
aList[largest] = tmp;
heapify(aList, largest);
}
}
建立大顶堆
void buildHeap(vector<int>& aList) {
auto len = aList.size();
for (int i = floor((len-1)/2); i >= 0 ; i--) {
heapify(aList, i);
}
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论