堆树是一棵完全二叉树，且每一个节点的值都大于等于或者小于等于其左右节点的值。通过这一结构可以快速找到堆中的最大值或最小值。

满二叉树：除了叶子节点，每个节点的度都为2 完全二叉树：二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布

小顶堆：根节点最小的堆
大顶堆：根节点最大的堆
微信截图_20210712102403.png

堆树的存储结构

由于完全二叉树的性质，堆树可以直接利用数组来存储，假设根节点在数组中下标为0，那么父节点和子节点的关系如下：

  1. 下标为 i 的节点其左节点下标为 2*i+1，位运算 (i << 1)+1
  2. 下标为 i 的节点其右节点下标为 2*i+2，位运算 (i << 1)+2
  3. 下标为 i 的节点其父节点下标为 (i-1)/2，位运算 (i-1) >> 1

微信截图_20210712105912.png

堆树的插入

堆树的插入操作也叫堆化，常用的插法是从尾部插入，时间复杂度为O(logN)

  1. 新节点统一插入到数组尾部
  2. 依次向上调整，直到满足小于（大于）父节点的要求

以小顶堆为例，在数组 {3, 5, 8, 7, 10, 12} 中插入 6 ，首先将6插入到数组尾部
微信截图_20210712154507.png
接着向上调整，与父节点比较，若小于父节点则需要交换位置，直到满足条件，完成插入。6小于8，所以6与8互换位置，6大于3，满足堆树条件，插入完成。
微信截图_20210712154906.png
微信截图_20210712155158.png

堆树的删除

为了保证完全二叉树的性质（最后一层节点一次靠左），不能直接将节点删除再把后续节点依次向上调整，正确的做法是

  1. 将要删除的节点与尾节点替换，删除尾节点
  2. 依次将节点向下调整，直到符合堆树条件

时间复杂度为O(logN)，以小顶堆为例，数组 {3, 5, 6, 7, 10, 12, 8}，删除根节点3，首先与尾节点交换位置，删除尾节点
微信截图_20210712160938.png
依次向下调整直到符合堆树条件
微信截图_20210712161831.png

代码实现

  1. /**
  2.  * @author :松岛安
  3.  * @slogan :社会主义码农
  4.  * @description :堆树结构实现
  5.  */
  6. public class HeapTree {
  8.     private static int[] heap;
  10.     private static int size;
  12.     public HeapTree(int capacity){
  13.         size = 0;
  14.         heap = new int[capacity+1];
  15.         Arrays.fill(heap, -1);
  16.     }
  18.     public boolean isFull(){
  19.         return size == heap.length;
  20.     }
  22.     public boolean isEmpty(){
  23.         return size == 0;
  24.     }
  26.     //获取父节点下标
  27.     public int getParent(int i){
  28.         if((i-1) >> 1 >= 0){
  29.             return (i-1) >> 1;
  30.         }else{
  31.             return -1;
  32.         }
  33.     }
  35.     //获取左子节点下标
  36.     public int getLeftChild(int i){
  37.         if((i<<1) + 1 <= heap.length){
  38.             return (i<<1) + 1;
  39.         }else{
  40.             return -1;
  41.         }
  42.     }
  44.     //获取右子节点下标
  45.     public int getRightChild(int i){
  46.         if((i<<1) + 2 <= heap.length){
  47.             return (i<<1) + 2;
  48.         }else{
  49.             return -1;
  50.         }
  51.     }
  53.     //查找最大孩子节点下标
  54.     public int getMaxChild(int i){
  55.         int leftChild = getLeftChild(i);
  56.         int rightChile = getRightChild(i);
  57.         if(leftChild < 0 || rightChile < 0){
  58.             return -1;
  59.         }
  60.         return heap[leftChild] >= heap[rightChile] ? leftChild : rightChile;
  61.     }
  63.     //获取最小孩子节点下标
  64.     public int getMinChild(int i){
  65.         int leftChild = getLeftChild(i);
  66.         int rightChile = getRightChild(i);
  67.         if(leftChild < 0 || rightChile < 0){
  68.             return -1;
  69.         }
  70.         return heap[leftChild] < heap[rightChile] ? leftChild : rightChile;
  71.     }
  73.     //大顶堆节点向上调整
  74.     public void bigHeapUp(int i){
  75.         int insertedValue = heap[i];
  76.         while (i > 0 && insertedValue > heap[getParent(i)]){
  77.             //向上调整
  78.             heap[i] = heap[getParent(i)];
  79.             i = getParent(i);
  80.         }
  81.         heap[i] = insertedValue;
  82.     }
  84.     //小顶堆节点向上调整
  85.     public void smallHeapUp(int i){
  86.         int insertedValue = heap[i];
  87.         while (i > 0 && insertedValue < heap[getParent(i)]){
  88.             //向上调整
  89.             heap[i] = heap[getParent(i)];
  90.             i = getParent(i);
  91.         }
  92.         heap[i] = insertedValue;
  93.     }
  95.     //大顶堆节点向下调整
  96.     public void bigHeapDown(int i){
  97.         int maxChild;
  98.         int temp = heap[i];
  99.         while (getRightChild(i) < size){
  100.             maxChild = getMaxChild(i);
  101.             if(temp > heap[maxChild]){
  102.                 break;
  103.             }
  104.             //孩子节点上移
  105.             heap[i] = heap[maxChild];
  106.             i = maxChild;
  107.         }
  108.         heap[i] = temp;
  109.     }
  111.     //小顶堆节点向下调整
  112.     public void smallHeapDown(int i){
  113.         int minChild;
  114.         int temp = heap[i];
  115.         while (getRightChild(i) < size){
  116.             minChild = getMinChild(i);
  117.             if(temp < heap[minChild]){
  118.                 break;
  119.             }
  120.             heap[i] = heap[minChild];
  121.             i = minChild;
  122.         }
  123.         heap[i] = temp;
  124.     }
  126.     //查找最大值或最小值
  127.     public int getRoot(){
  128.         return heap[0];
  129.     }
  131.     //大顶堆插入
  132.     public void bigInsert(int value){
  133.         if(isFull()){
  134.             throw new RuntimeException("the heap is full");
  135.         }
  136.         heap[size] = value;
  137.         size ++;
  138.         bigHeapUp(size-1);
  139.     }
  141.     //小顶堆插入
  142.     public void smallInsert(int value){
  143.         if(isFull()){
  144.             throw new RuntimeException("the heap is full");
  145.         }
  146.         heap[size] = value;
  147.         size ++;
  148.         smallHeapDown(size-1);
  149.     }
  151.     //大顶堆删除
  152.     public void bigDelete(int index){
  153.         if(isEmpty()){
  154.             throw new RuntimeException("the heap is empty");
  155.         }
  156.         int deleteNode = heap[index];
  157.         heap[index] = heap[size - 1];
  158.         size --;
  159.         bigHeapDown(index);
  160.     }
  162.     //小顶堆删除
  163.     public void smallDelete(int index){
  164.         if(isEmpty()){
  165.             throw new RuntimeException("the heap is empty");
  166.         }
  167.         int deleteNode = heap[index];
  168.         heap[index] = heap[size - 1];
  169.         size --;
  170.         smallHeapDown(index);
  171.     }
  172. }

堆排序

堆排序就是将数组先构造成一棵堆树，然后在这基础上进行排序。假设有一个数组 {8,4,21,6,3,1,26,14,18}，要讲数组从小到大进行排序，其堆树结构如图
微信截图_20210712164259.png
排序过程

  1. 从最后一个非叶子节点开始，从后往前开始堆化（叶子节点下没有节点可以进行比较），构建一棵大(小)顶堆
  2. 将堆顶节点与最后一个节点进行替换，根节点重新开始堆化，记录最后一个节点（该元素已经是最大(小)的元素，下次不必再与该元素交换），依次往后进行排序

堆化

找到第一个非叶子节点6，开始进行堆化
微信截图_20210712165947.png
第二个非叶子节点21
微信截图_20210712170252.png
第三个非叶子节点4
微信截图_20210712171001.png
第四个非叶子节点8
微信截图_20210712171420.png
至此，我们的大顶堆构建完毕。

排序

先将堆顶节点与尾节点进行替换，然后重新开始堆化
微信截图_20210712172806.png

重复上面操作
微信截图_20210712173241.png
微信截图_20210712173509.png
微信截图_20210712173652.png
微信截图_20210712173911.png
微信截图_20210712174053.png
微信截图_20210712174437.png
微信截图_20210712174552.png
至此，整个排序工作完成

代码实现

  1. public class HeapSort {
  3.     /*
  4.      * @Author 松岛安
  5.      * @Description 大顶堆堆化
  6.      * @Param data 数组
  7.      * @Param start 开始位置
  8.      * @Param end 结束位置,记录上次已完成排序的节点
  9.      * */
  10.     public static void maxHeap(int[] data, int start, int end){
  11.         int parent = start;
  12.         //获取左子节点下标
  13.         //为什么不用右节点判断? 因为有可能出现2*start+2>end,而2*start+1=end的情况，导致左节点没有进行堆化
  14.         int son = 2 * start + 1;
  16.         //为什么不能是 son<=end,因为下标为end的节点已经完成堆化，不需要再进行交换，end参数的意思是end-1之前的才需要堆化，end及end之后的不需要堆化
  17.         while(son < end){
  18.             int temp = son;
  19.             //获取最大子节点下标
  20.             //为什么不能是 son+1<=end,因为小标为end的节点已经完成堆化，不需要再进行交换，end参数的意思是end-1之前的才需要堆化，end及end之后的不需要堆化
  21.             if(son+1 < end && data[son] < data[son+1]){
  22.                 temp = son + 1;
  23.             }
  24.             //如果堆化父节点大于子节点，堆化完成
  25.             if(data[parent] > data[temp]){
  26.                 return;
  27.             }else{
  28.                 //父节点与子节点交换位置
  29.                 int t = data[parent];
  30.                 data[parent] = data[temp];
  31.                 data[temp] = t;
  32.                 //重新调整父节点与子节点下标，开始下一轮堆化
  33.                 parent = temp;
  34.                 son = 2*parent +1;
  35.             }
  36.         }
  37.         return;
  38.     }
  40.     public static void heapSort(int[] data){
  41.         //尾节点下标
  42.         /*int len = data.length-1;*/
  43.         int len = data.length;
  44.         //从第一个非叶子节点依次向上堆化
  45.         //len = data.length-1,会造成最后一个节点没有堆化(因为堆化中的比较是son<end而不是son<=end,相等进入不了下一次循环),但这不影响后续操作,因为最后一个节点会与堆顶进行互换
  46.         //最后一个节点要堆化则 len = data.length
  47.         for(int i = (len-2)>>1; i>=0; i--){
  48.             maxHeap(data, i, len);
  49.         }
  50.         //堆顶和尾节点互换，i--，继续进行排序
  51.         for(int i = len-1; i>=0; i--){
  52.             int temp = data[i];
  53.             data[i] = data[0];
  54.             data[0] = temp;
  55.             //互换后从新进行堆化,这里最后一个节点已经排好序,不用堆化,第一次堆化时i=data.length-1,证明了最后一个节点没有堆化
  56.             maxHeap(data, 0, i);
  57.         }
  58.     }
  61.     public static void main(String[] args) {
  62.         int[] data = new int[]{8,6,12,45,78,2,36,54};
  63.         heapSort(data);
  64.         System.out.println(Arrays.toString(data));
  65.     }