堆(Heap)是計算機科學中一類特殊的資料結構的統稱。
堆通常是一個可以被看做一棵完全二叉樹的數組對象。
堆滿足下列性質：
堆中某個節點的值總是不大于或不小于其父節點的值。
堆總是一棵完全二叉樹。
堆是利用完全二叉樹的結構來維護一組資料，然後進行相關操作，一般的操作進行一次的時間複雜度在 O(1)~O(logn) 之間，堆通常用于動态配置設定和釋放程式所使用的對象。
若為優先隊列的使用場景，普通數組或者順序數組，最差情況為 O(n^2)，堆這種資料結構也可以提高入隊和出隊的效率。
入隊
出隊
普通數組
O(1)
O(n)
順序數組
堆
O(logn)
O(log)
二叉堆是一顆完全二叉樹，且堆中某個節點的值總是不大于其父節點的值，該完全二叉樹的深度為 k，除第 k 層外，其它各層 (1～k-1) 的結點數都達到最大個數，第k 層所有的結點都連續集中在最左邊。
其中堆的根節點最大稱為最大堆，如下圖所示：
我們可以使用數組存儲二叉堆，右邊的标号是數組的索引。
假設目前元素的索引位置為 i，可以得到規律：
源碼包下載下傳：Download
package runoob.heap;
/**
* 堆定義
*/
public class MaxHeap<T> {
private T[] data;
private int count;
// 構造函數, 構造一個空堆, 可容納capacity個元素
public MaxHeap(int capacity){
data = (T[])new Object[capacity+1];
count = 0;
}
// 傳回堆中的元素個數
public int size(){
return count;
// 傳回一個布爾值, 表示堆中是否為空
public boolean isEmpty(){
return count == 0;
// 測試 MaxHeap
public static void main(String[] args) {
MaxHeap<Integer> maxHeap = new MaxHeap<Integer>(100);
System.out.println(maxHeap.size());
}