开发笔记:面试必知必会|理解堆和堆排序

//数组下标范围
i<=n && i>=1
//根结点下标为1
root_index = 1
//层次遍历第i个结点的值等于数组第i个元素
value(i) = array[i]
//堆中第i个元素的左孩子下标i*2
left_child_index(i) = i*2
//堆中第i个元素的右孩子下标i*2+1
right_child_index(i) = i*2+1
//堆中第i个元素的父结点下标i/2
parent(i) = i/2

//siftup运行的前置条件
heap(1,n-1) == True
void siftup(n)
i = n
loop:
// 循环停止条件一
// 已经是根结点
if i == 1:
break;
p = i/2
// 循环停止条件二
// 调整结点大于等于在此位置的父结点
if a[p] <= a[i]
break;
swap(a[p],a[i])
// 继续向上循环
i = p

heap(2,n) == True
void siftdn(n)
i = 1
loop:
// 获取理论上的左孩子下标
c = 2*i
// 如果左孩子下标已经越界
// 说明当前已经是叶子结点
if c > n:
break;
//如果存在右孩子
// 则获取左右孩子中更小的一个
// 和父结点比较
if c+1 <= n:
if a[c] > a[c+1]
c++
// 父结点小于等于左右孩子结点则停止
if a[i] <= a[c]
break;
// 父结点比左右孩子结点大
// 则与其中较小的孩子结点交换
// 也就是让原来的孩子结点成为父结点
swap(a[i],a[c])
// 继续向下循环
i = c

//leetcode 215th the Kth Num
//Source Code:C++
class Solution {
public:
//调整以当前节点为根的子树为小顶堆
int heapadjust(vector<int> &nums,int curindex,int len){
int curvalue = nums[curindex];
int child = curindex*2+1;
while(child<len){
//左右孩子中较小的那个
if(child+1 nums[child+1]){
child++;
}
//当前父节点比左右孩子其中一个大
if(curvalue > nums[child]){
nums[curindex]=nums[child];
curindex = child;
child = curindex*2+1;
}else{
break;
}
}
nums[curindex]=curvalue;
return 0;
}
int findKthLargest(vector<int>& nums, int k) {
//边界条件
if(nums.size()<k)
return -1;
//建立元素只有K个的小顶堆
//截取数组的前k个元素
vector<int> subnums(nums.begin(),nums.begin()+k);
int len = nums.size();
int sublen = subnums.size();
//将数组的前k个元素建立小顶堆
for(int i=sublen/2-1;i>=0;i--){
heapadjust(subnums,i,sublen);
}
//建立好小顶堆之后 开始逐渐吸收剩余的数组元素
//动态与堆顶元素比较 替换
for(int j=k;j){
if(nums[j]<=subnums[0])
continue;
subnums[0] = nums[j];
heapadjust(subnums,0,sublen);
}
return subnums[0];
}
};