先提个问题，完全二叉树/满二叉树，区别？前者是指每一层都是紧凑靠左排列，最后一层可能未排满，后者是一种特殊的完全二叉树，每层都是满的，即节点总数和深度满足N=(2^n) -1。堆Heap，一堆苹果，为了卖相好，越好看的越往上放，就是大顶堆；为了苹果堆的稳定，质量越小越往上放，就是小顶堆；堆首先是完全二叉树，但只确保父节点和子节点大小逻辑，不关心左右子节点的大小关系，通常是一个可以被看做一棵树的数组对象，是个很常见的结构，比如BST对象，都与堆有关系，今天就说下这个重要的数据结构和应用。
准备：
Idea2019.03/Gradle6.0.1/Maven3.6.3/JDK11.0.4
难度： 新手--战士--老兵--大师
目标：
1.堆的构建和调整算法
1 优先级队列
为理解堆的原理，先看优先级队列，它是一种数据结构，插入或者删除元素的时候，元素会自动排序，(优先级不是狭义的数值大小，但为了通俗理解，这里以字母序为例)，通常使用数组存储，我们可以按照下图进行转换，序号 0 不用：
优先级队列的实现(Java版)：
public class PriorityQueue<Key extends Character> {
/** 存储元素的数组 */
private Key[] keys;
private int N = 0;
public PriorityQueue(int capacity){
// 下标0不用，多分配一个单位
keys = (Key[]) new Character[capacity + 1];
}
public Key max(){
return keys[1];
}
public void insert(Key e){
N ++;
keys[N] = e;
swim(N);
}
public Key delMax(){
Key max = keys[1];
swap(1,N);
keys[N] = null;
N --;
// 让第一个元素下沉到合适的位置
sink(1);
return max;
}
/** 上浮第k个元素*/
private void swim(int k){
// 比父节点小，即进行交换，直到根
while (k > 1 && less(parent(k),k)){
swap(k,parent(k));
k = parent(k);
}
}
/** 下沉第 k 个元素*/
private void sink(int k){
while(k < N){
int small = left(k);
if (right(k) < N && less(right(k),left(k))){
small = right(k);
}
if (less(k,small)){
swap(k,small);
k = small;
}
}
}
private void swap(int i,int j){
Key temp = keys[i];
keys[i] = keys[j];
keys[j] = temp;
}
/** 元素i和j大小比较*/
private boolean less(int i,int j){
// 'a' - 'b' = -1 ;
return keys[i].compareTo(keys[j]) > 0;
}
/** 元素i的父节点*/
private int parent(int i){
return i/2;
}
/** 元素i的左子节点*/
private int left(int i){
return i * 2;
}
/** 元素i的右子节点*/
private int right(int i){
return i * 2 + 1;
}
}
以上代码解析：
1 swim 上浮，对于元素k，是否需要上浮，仅需与其父节点比较，大于父节点则交换，迭代直到根节点；
2 sink 下沉，对于元素k，是否需要下沉，需先比较其左右子节点，找出左右子节点中较小者，较小者若比父节点大，则交换，迭代直到末尾元素；
3 insert 插入，先将元素放到数组末尾位置，再对其进行上浮操作，直到合适位置；
4 delMax 删除最大值，大根堆，故第一个元素最大，先将首末元素交换，再删除末尾元素，再对首元素下沉操作，直到合适位置；
总结：以上只是Java简化版，java.util.PriorityQueue 是JDK原版，客官可自行研究。但设计还是非常有技巧的，值得思考一番，假设 insert 插入到首位，会导致数组大量元素移动。delMax 若直接删除首位最大值，则需要进一步判断左右子节点大小，并进行先子节点上浮再首元素下沉操作。
有了这个堆结构，就可以进行堆排序了，将待排数全部加入此堆结构，然后依次取出，即成有序序列了！
2 堆排序
如要求不使用上述堆数据结构。思路(升序为例)：将数组构建为一个大顶堆，首元素即为数组最大值，首尾元素交换；排除末尾元素后调整大顶堆，则新的首元素即为次最大值，交换首尾并再排除末尾元素；如此循环，最后的数组即为升序排列。
public class HeapSort02 {
public static void main(String []args){
int []arr = {2,1,8,6,4,7,3,0,9,5};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int []arr){
int len = arr.length;
// 创建一个大顶堆
for(int i = (int) Math.ceil(len/2 - 1); i >= 0; i--){
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,len);
}
// 交换首尾元素，并重新调整大顶堆
for(int j = len-1;j > 0;j--){
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
/** 迭代写法*/
public static void adjustHeap(int []arr,int i,int length){
int temp = arr[i];
for (int k = 2*i + 1; k < length; k=k*2 + 1) {
// 注意这里的k + 1 < length
// 如果右子节点大于左子节点，则比较对象为右子节点
if (k + 1 < length && arr[k] < arr[k+1]){
k++;
}
if (arr[k] > temp){
// 不进行值交换
arr[i] = arr[k];
i = k;
}
else{
break;
}
}
arr[i] = temp;
}
/** 递归写法*/
private static void adjustHeap2(int[] arr, int i, int len){
int left = 2 * i + 1;
int right = 2 * i + 2;
int maxIndex = i;
// 注意这里的 left < len
if (left < len && arr[left] > arr[maxIndex]){
maxIndex = left;
}
if (right < len && arr[right] > arr[maxIndex]){
maxIndex = right;
}
if (maxIndex != i){
swap(arr,i,maxIndex);
adjustHeap2(arr,maxIndex,len);
}
}
/** 交换元素 */
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
以上代码解析：
1完全二叉树结构中，如果根节点顺序号为 0，总节点数为 N，则最末节点的父节点即为最后一个非叶子节点，顺序号为 ceil(N/2 -1)，
2 adjustHeap2 为啥使用三个参数，不用中间的参数可以？使用三个参数，是为了进行递归调用，因为递归肯定是缩小计算规模，而这里的形参arr和len是固定不变的；
3 adjustHeap是非递归写法，不用中间的参数可以？调用一在“构建大顶堆”处，可写为函数体内初始化 i，并形成双重 for 循环；调用二在“重新调整大顶堆”处，可见中间参数为 0，可直接去掉。故回答是可以！但需要调整写法，且影响该方法复用，这里直接写为三个形参的函数更为优雅而已。
4非递归写法理解：类似插入排序思想(依次移动并找到合适的位置再插入)，先将 arr[i] 取出，然后此节点和左右子树进行比较，如子树更大则子节点上升一层，使用for循环迭代到最终位置，并进行赋值；
以 i=0 为例：
5递归方式理解：定位目标元素的左右子树，若子树值更大，则进行值交换，且因为子树发生了变化，故需要对子树进行递归处理；
3 前K个最大的数
在N个数中找出前K个最大的数：思路：从N个数中取出前K个数，形成一个数组[K]，将该数组调整为一个小顶堆，则可知堆顶为K个数中最小值，然后依次将剩余 N-K 个数与堆顶比较，若大于，则替换掉并调整堆，直到所有元素加入完毕，堆中元素即为目标集合。
public class HeapSort {
public static void main(String[] args) {
int[] arr = new int[100];
for (int i = 0; i < 100; i++) {
arr[i] = i + 1;
}
// 前10个最大的数
int k = 10;
// 构造小顶堆
for (int i = (int) Math.ceil(k/2 - 1); i >= 0; i--) {
adjustHeap(arr,i,k);
}
// 依次比较剩余元素
for (int i = 10; i < arr.length; i++) {
if (arr[i] > arr[0]){
swap(arr,0,i);
adjustHeap(arr,0,k);
}
}
// 输出结果
for (int i = 0; i < 10; i++) {
System.out.print(arr[i]+"-");
}
}
/** 非迭代写法 ,对arr[i]进行调整 */
private static void adjustHeap(int[] arr,int i,int length){
int temp = arr[i];
for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
// 因第一次循环中可能越界，故需要 k+1 < length
if (k + 1 < length && arr[k] > arr[k + 1]){
k++;
}
if (arr[k] < temp){
arr[i] = arr[k];
i = k;
}
else {
break;
}
}
arr[i] = temp;
}
/** 递归写法 */
private static void adjustHeap2(int[] arr,int i,int length){
int left = i * 2 + 1;
int right = i * 2 + 2;
int samller = i;
if (left < length && arr[left] > arr[samller]){
samller = right;
}
if (right < length && arr[right] > arr[samller]){
samller = right;
}
if (samller != i){
swap(arr,i,samller);
adjustHeap2(arr,samller,length);
}
}
/** 交换元素 */
public static void swap(int []arr,int a ,int b){
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
以上代码解析：按照"初始化—构建小顶堆—比较调整—输出结果"执行。注意for循环中，因第一次循环中未使用for语句条件判断，可能越界，故需要 k+1 < length
。
输出结果如下：
请看官思考，如果需求变为找出N个数中找出前K个最小的数,该如何实现? 建议动脑且动手的写一遍！因为魔鬼在细节！
全文完！
我近期其他文章：
1 Dubbo学习系列之十九（Apollo配置中心） 2 聊聊算法——二分查找算法深度分析 3 DevOps系列——Jenkins/Gitlab自动打包部署 4 DevOps系列——Jenkins私服 5 DevOps系列——Gitlab私服
只写原创，敬请关注
