一、堆结构
1、堆在结构上是一颗完全二叉树
2、大根堆和小根堆
大根堆：其特点在于每个节点的值都大于或等于其子节点的值
小根堆：其每个非叶子节点的值都小于或等于其子节点的值
3、树调整的代价logN
4、调整后为什么还是大根堆
若原堆是大根堆，最后一个数它肯定是整个堆里最小的数
假设它是最小的数，将它挪到顶，就必然要对每棵子树的头结点进行判断
5、自己实现堆结构代码
package class04;public class Code02_Heap01 {public static class MyMaxHeap {private int[] heap; //一个数组作为堆private final int limit;private int heapSize;public MyMaxHeap(int limit) {heap = new int[limit];this.limit = limit;heapSize = 0;}public boolean isEmpty() {return heapSize == 0;}public boolean isFull() {return heapSize == limit;}public void push(int value) {if (heapSize == limit) { //heapSize到极限了throw new RuntimeException("heap is full");}heap[heapSize] = value; //value放在heapSize位置heapInsert(heap, heapSize++);}/*** 用户获取最大值，返回最大值并且在大根堆中把最大值删掉* 剩下的数，依然保持大根堆组织* @return*/public int pop() {int ans = heap[0]; //返回0位置的数swap(heap, 0, --heapSize); //把最后一个位置的值和0位置的值交换heapify(heap, 0, heapSize); //从0位置开始，做heapifyreturn ans;}public void heapInsert(int[] arr, int index) {// arr[index]是新进来的数// 停止条件：// （1）arr[index]不比arr[index父]大了，停// （2）当heapSize=0，arr[(index - 1) / 2]是它自己，停while (arr[index] > arr[(index - 1) / 2]) { //比较arr[index]节点值和它的父亲节点的值swap(arr, index, (index - 1) / 2); //交换index = (index - 1) / 2; //然后index来到它父亲节点的位置}}/*** 从index位置往下看，树不断的下沉* 停止条件：我的孩子都不再比我大，或者已经没有孩子了* @param arr* @param index* @param heapSize*/private void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1; //左孩子的下标while (left < heapSize) { //左孩子没越界// 左右两个孩子中，谁大，谁把自己的下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// 判断值有没有父节点大largest = arr[largest] > arr[index] ? largest : index;// 说明左右孩子都没有index大if (largest == index) {break;}swap(arr, largest, index);index = largest; //index位置往下沉left = index * 2 + 1; //继续找下一步的左孩子}}private void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}}/*** 绝对对的大根堆* 用来比较*/public static class RightMaxHeap {private int[] arr;private final int limit;private int size;public RightMaxHeap(int limit) {arr = new int[limit];this.limit = limit;size = 0;}public boolean isEmpty() {return size == 0;}public boolean isFull() {return size == limit;}//加的时候直接加在最后面public void push(int value) {if (size == limit) {throw new RuntimeException("heap is full");}arr[size++] = value;}//弹出最大值的时候，每次都全部遍历一遍public int pop() {int maxIndex = 0;for (int i = 0; i < size; i++) {if (arr[i] > arr[maxIndex]) {maxIndex = i;}}int ans = arr[maxIndex];arr[maxIndex] = arr[--size];return ans;}}public static void main(String[] args) {int value = 1000;int limit = 100;int testTimes = 1000000; //测试100万次，随机的次数加入和弹出for (int i = 0; i < testTimes; i++) {int curLimit = (int) (Math.random() * limit) + 1;MyMaxHeap my = new MyMaxHeap(curLimit);RightMaxHeap test = new RightMaxHeap(curLimit);int curOpTimes = (int) (Math.random() * limit);for (int j = 0; j < curOpTimes; j++) {if (my.isEmpty() != test.isEmpty()) {System.out.println("Oops!");}if (my.isFull() != test.isFull()) {System.out.println("Oops!");}if (my.isEmpty()) { //如果我是空的，共同加入int curValue = (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else if (my.isFull()) { //如果我是满的，共同弹出if (my.pop() != test.pop()) {System.out.println("Oops!");}} else { //如果不空，不满if (Math.random() < 0.5) { //以0.5的概率加入int curValue = (int) (Math.random() * value);my.push(curValue);test.push(curValue);} else { //以剩下0.5的概率弹出if (my.pop() != test.pop()) {System.out.println("Oops!");}}}}}System.out.println("finish!");}}
二、堆排序
1、用户给你一串数，是无序的
思路：
（1）先将这串数，变为大根堆，即第一步
（2）在利用叶子下沉完成从小到大排序
2、代码
package class04;public class Code04_HeapSort {// 堆排序，整个里面没有递归，额外空间复杂度O(1)public static void heapSort(int[] arr) {if (arr == null || arr.length < 2) {return;}System.out.println("step1...start");// 经典堆排序// 第一步// 总体是O(N*logN)for (int i = 0; i < arr.length; i++) { //这一步是O(N)heapInsert(arr, i); //这一步是O(logN)}// 这是上面堆排序的优化
// for (int i = arr.length - 1; i >= 0; i--) {
// heapify(arr, i, arr.length);
// }System.out.println("step1...end");int heapSize = arr.length;swap(arr, 0, --heapSize);for (int i : arr) {System.out.print(i + " ");}System.out.println();System.out.println("step2...start");// 第二步// 总体是O(N*logN)while(heapSize > 0) { //这一步是O(N)heapify(arr, 0, heapSize); //这一步是O(logN)swap(arr, 0, --heapSize); //这一步是O(1)for (int i : arr) {System.out.print(i + " ");}System.out.println();}System.out.println("step2...end");}public static void heapInsert(int[] arr, int index) {while(arr[index] > arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index = (index - 1) / 2;for (int i : arr) {System.out.print(i + " ");}System.out.println();}}/*** 从index位置往下看，树不断的下沉* 停止条件：我的孩子都不再比我大，或者已经没有孩子了* @param arr* @param index* @param heapSize*/public static void heapify(int[] arr, int index, int heapSize) {int left = index * 2 + 1; //左孩子的下标while (left < heapSize) { //左孩子没越界// 左右两个孩子中，谁大，谁把自己的下标给largestint largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;// 判断值有没有父节点大largest = arr[largest] > arr[index] ? largest : index;// 说明左右孩子都没有index大if (largest == index) {break;}swap(arr, largest, index);index = largest; //index位置往下沉left = index * 2 + 1; //继续找下一步的左孩子}}public static void swap(int[] arr, int i, int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}public static void main(String[] args) {int[] arr = {6, 5, 3, 2, 1, 0, 9};heapSort(arr);for (int i : arr) {System.out.print(i + " ");}System.out.println();}
}
执行结果：
step1...start
6 5 9 2 1 0 3
9 5 6 2 1 0 3
step1...end
3 5 6 2 1 0 9
step2...start
0 5 3 2 1 6 9
1 2 3 0 5 6 9
0 2 1 3 5 6 9
1 0 2 3 5 6 9
0 1 2 3 5 6 9
0 1 2 3 5 6 9
step2...end
0 1 2 3 5 6 9
3、说明
（1）先让整个数组都变成大根堆结构
从上到下的方法，时间复杂度为O(N*logN)
从下到上的方法，时间复杂度为O(N)
（2）把堆的最大值和堆末尾的值交换，然后减少堆的大小之后，再去调整堆，一直周而复始，时间复杂度为O(N*logN)
（3）堆的大小减小成0之后，排序完成
三、堆结构小结
1、堆结构就是数组实现的完全二叉树
2、完全二叉树中如果每棵子树的最大值都在顶部就是大根堆
3、完全二叉树中如果每棵子树的最小值都在顶部就是小根堆
4、堆结构的heapInsert与heapify操作
5、堆结构的增大和减少
6、优先级队列结构，就是堆结构
四、语言提供的堆结构 VS 手写的堆结构
1、取决于，你有没有动态改信息的需求
2、语言提供的堆结构，如果你动态改数据，不保证依然有序
3、手写堆结构，因为增加了对象的位置表，所以能够满足动态改信息的需求