9.1.概述
概念：
根节点是自己所在子树中的最值的完全二叉树。
根节点是所在子树的最大值，称为大顶堆。
根节点是所在子树的最小值，称为小顶堆。
堆的任何子树的根节点到子树上的任意节点，路径上的节点都是有序的，大顶堆为降序，小顶堆为升序。
此处展示一个大顶堆：
作用：
堆一般用来在大量数据中找到前N大或者前N小的数据。
存储：
一般用数组来存储堆，首先因为堆一般是从空树开始建立的，不论如何操作其一定会是一颗完全二叉树，不存在大量非叶子结点没有左右孩子的情况，所以用数组来表示不会造成内存浪费。其次堆的删除操作需要从叶节点反向向根结点方向遍历，链表结构不太好支持这种反向遍历。
9.2.操作
9.2.1.插入
堆的插入采用尾插法，新入堆的节点挂在最后一个叶节点上，然后往上浮（交换位置）。
假设已有一颗树，是按照44、25、31、18、10的插入顺序建树的。
假设插入的是20：
假设插入的是35：
9.2.2.删除
堆的删除操作，从叶子结点开始删除的话，直接删除即可，不会有任何影响，只有在删除非叶子结点时才要考虑进行结点间的调整，保持堆是大顶堆或者小顶堆。
堆在使用时每次弹出的都是堆顶的数据，因此删除操作都是针对堆顶元素的，此处以大顶堆的删除操作为例：
用最末尾的叶节点替换根节点，然后新的根节点与左右孩子比较是否为最大值，若不为最大值，则与参与比较的三个节点中的最大值互换位置，然后递归以上过程，出口为到达叶节点或者到达合适位置。
9.2.3.代码实现
package linearStructure.tree.heap; import java.util.ArrayList; import java.util.List; public class MaxTopHeap { //存储堆的数组 private int[] heap; //堆的最大存储容量 private int maxSize; //当前堆的存储数量 private int heapSize; public MaxTopHeap(int maxSize) { this.heap = new int[maxSize]; this.maxSize = maxSize; this.heapSize = 0; } // 判断是否为空的方法 public boolean isEmpty() { return heapSize == 0; } // 判断是否填满 public boolean isFull() { return heapSize == maxSize; } // 获取堆顶的值 public int peek() throws Exception { if (heapSize == 0) { throw new Exception("heap is empty"); } return heap[0]; } // 往堆中添加值 public void insert (int value) throws Exception { if (heapSize == maxSize) { throw new Exception("head is full"); } heap[heapSize] = value; heapSize++; buildMaxHeap(heap); } // 删除堆顶值 public int poll() throws Exception { if (heapSize == 0) { throw new Exception("heap is empty"); } int ans = heap[0]; swap(heap,0,--heapSize); buildMaxHeap(heap); return ans; } // 建大顶堆 private int[] buildMaxHeap(int[] array) { for (int i = (heapSize-2)/2; i >= 0; i--) { adjustDownToUp(array,i,heapSize); } return array; } private void adjustDownToUp(int[] array, int index, int length) { int temp = array[index]; for (int i = 2*index+1; i < length; i = 2*i+1) { if (i < length-1 && array[i] < array[i+1]) { i++; } if (temp >= array[i]) { break; } else { array[index] = array[i]; index = i; } } array[index] = temp; } // 交换元素值 private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // 获取所有元素 public List<Integer> getAllElements() { List<Integer> ans = new ArrayList<>(); for (int i = 0; i < heapSize; i++) { ans.add(heap[i]); } return ans; } }
