1. 堆的特點
- 堆的邏輯結構是數組，內存結構是完全二叉樹.完全二叉樹即只有最后一層才有葉子節點.
- 堆又分為大頂堆與小頂堆. 大頂堆的特點是 : 父親節點比孩子節點的都要大. 小頂堆的特點與其相反.
- Java的優先級隊列(PriorityQueue)的底層實現即用到了小頂堆. 所以下文我們就用Java代碼來實現小頂堆.
- 本文沒有像實現棧或隊列那樣使用了泛型，為了方便省去了泛型的步驟.
2. 小頂堆的實現
(1). 主要操作 :?
- 堆化:傳入一個數組，從下到上，最后一個非葉子節點開始，再從上到下不斷進行下沉操作.
- offer()添加元素:從數組尾部添加元素，不斷上浮.
- poll()彈出堆首元素.將堆首元素與最后一個葉子節點互換，size--，再從堆首開始下沉操作即可.
(2). 代碼實現
//代碼實現小頂堆
//邏輯結構是數組
public class MyHeap {private int size;private int[] heap;public MyHeap(int capacity) {heap = new int[capacity];}//堆化public void heapify(int[] arr) {for (int i = 0; i < arr.length; i++) {heap[i] = arr[i];}size = arr.length;//第一步 : 找到最后一個非葉子節點//第二步 : 從該節點出發, 從后往前, 以此堆化//size - 1即最后一個葉子節點, 依據公式, 該則為葉子節點的父親節點for (int parent = (size - 1) / 2; parent >= 0; parent--) {int leftChild = parent*2 + 1;int rightChild = parent*2 + 2;int min = parent;//如果存在左孩子, 而且父親節點比孩子節點要大if (leftChild < size && heap[min] > heap[leftChild]) {min = leftChild;}//如果存在右孩子, 而且右孩子的值比左孩子和父親還要小if (rightChild < size && heap[min] > heap[rightChild]) {min = rightChild;}//如果最小值不是父親, 那么需要下沉if (min != parent) {down(parent);}}}private void swap(int a, int b) {int temp;temp = heap[a];heap[a] = heap[b];heap[b] = temp;}private void down(int parent) {int leftChild = parent*2 + 1;int rightChild = parent*2 + 2;int min = parent;if (leftChild < size && heap[min] > heap[leftChild]) {min = leftChild;}if (rightChild < size && heap[min] > heap[rightChild]) {min = rightChild;}if (min != parent) {swap(min, parent);down(min);}}//向堆中添加元素, 如果該添加的元素比父親節點(如果有的話)要小,//則需要上浮public void offer(int a) {if (size > heap.length) {return;}heap[size] = a;int child = size;size++;int parent;while (child >= 0) {parent = (child - 1) / 2;//如果添加的元素要比父親要小if (heap[parent] > heap[child]) {swap(parent, child);child = parent;} else {//如果添加后父親節點仍然符合小頂堆, 那么退出循環, 無需再上浮break;}}}//返回堆頂元素public int peek() {return heap[0];}//彈出堆頂元素//第一步 : 將最后一個葉子節點與堆頂元素互換, size--//第二步 : 從堆頂開始不斷下沉public int poll() throws Exception {if (size == 0) {throw new Exception();}int value = peek();swap(0, size - 1);size--;//不斷下沉int parent = 0;down(parent);return value;}
}
3. 單元測試
public class MyHeapTest {@Testpublic void test1() throws Exception {MyHeap heap = new MyHeap(10);int[] arr = new int[]{9, 12, 4, 3, 1};heap.heapify(arr);System.out.println(heap.peek());//1System.out.println(heap.poll());//1System.out.println(heap.peek());//3heap.offer(0);System.out.println(heap.peek());//0}
}
)
)
