其他
面试必知必会|理解堆和堆排序
堆是计算机科学中的一种特别的树状数据结构。
若是满足以下特性，即可称为堆：给定堆中任意节点P和C，若P是C的母节点，那么P的值会小于等于C的值。若母节点的值恒小于等于子节点的值，此堆称为最小堆；反之称为最大堆。
堆始于J. W. J. Williams在1964年发表的堆排序，当时他提出了二叉堆树作为此算法的数据结构，堆在戴克斯特拉算法和带优先级队列中亦为重要的关键。
维基百科-堆
堆数据结构的定义
堆的数组表示
堆的调整函数
堆排序实践
1.堆的简介
元素顺序：
在堆中任何结点与其子结点的大小都遵守数值大小关系。
A. 如果结点大于等于其所有子结点，也就是堆的根是所有元素中最大的，这种堆称为大根堆(大顶堆、最大堆)；
B. 如果结点小于等于其所有子结点，也就是堆的根是所有元素中最小的，这种堆称为小根堆(小顶堆、最小堆)；
C. 大根堆/小根堆只是约定了父结点和子结点的大小关系，但是并不约束子结点的相对大小和顺序；
如图为小根堆结构：
树的形状：
2.堆的数组表示
//数组下标范围i<=n && i>=1//根结点下标为1root_index = 1//层次遍历第i个结点的值等于数组第i个元素value(i) = array[i]//堆中第i个元素的左孩子下标i*2left_child_index(i) = i*2//堆中第i个元素的右孩子下标i*2+1right_child_index(i) = i*2+1//堆中第i个元素的父结点下标i/2parent(i) = i/23.堆的调整函数
siftup函数的原理
//siftup运行的前置条件heap(1,n-1) == Truevoid siftup(n) i = n loop: // 循环停止条件一 // 已经是根结点 if i == 1: break; p = i/2 // 循环停止条件二 // 调整结点大于等于在此位置的父结点 if a[p] <= a[i] break; swap(a[p],a[i]) // 继续向上循环 i = pheap(2,n) == Truevoid 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 siftdn调整过程演示
在头部元素更新为21的调整过程如图：
4.堆排序
//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<len && nums[child] > 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<len;j++){ if(nums[j]<=subnums[0]) continue; subnums[0] = nums[j]; heapadjust(subnums,0,sublen); } return subnums[0]; }};上述代码中的heapadjust本质上就是siftdn函数。
5.总结：
6.参考资料：
《编程珠玑》 第14章 堆
7.往期精彩：
理解Redis持久化
Linux中的各种锁及其基本原理
浅析CPython的全局解释锁GIL
浅谈Linux下Socket选项设置
深入理解IO复用之epoll