什么是堆？ 堆是滿足下面兩個(gè)條件的一種二叉樹
- 它是一棵完全二叉樹；
- 堆中每個(gè)節(jié)點(diǎn)的值都必須大于等于（大根堆）或者小于等于（小根堆）其子樹中每個(gè)節(jié)點(diǎn)的值。
完全二叉樹是指除了最后一層，其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿的，最后一層的節(jié)點(diǎn)都靠左排列
我們看幾個(gè)例圖
image.png
其中1,2是大根堆，3,4是小根堆。從圖中我們也可以看出來，同一組數(shù)據(jù)排成的堆可能有多種形式。
存儲
因?yàn)槎咽且豢猛耆鏄?，所以我們通常使用?shù)組來存儲它。節(jié)約空間也好定位父節(jié)點(diǎn)或者子節(jié)點(diǎn)。為了計(jì)算子節(jié)點(diǎn)方便，通常從下標(biāo)為1的位置開始存儲，如果i是父節(jié)點(diǎn)那么2i， 2i + 1就是子節(jié)點(diǎn)。
如下圖所示
添加元素
添加元素通常是在數(shù)組的最末尾添加，這樣添加之后數(shù)組仍然滿足堆的特性1，但是不滿足特性2了，所以必須進(jìn)行調(diào)整，我們將這個(gè)調(diào)整過程稱為heapify.
方法很簡單： 就是順著節(jié)點(diǎn)所在的路徑，往上對比，需要換位置的就交換
下面是java代碼實(shí)現(xiàn)：
public void insert(int value){
if(count >= capacity) return ;
data[++count] = value;
int current = count;
int parentIndex = count/2;
while(parentIndex > 0 && data[parentIndex] < value){
data[current] = data[parentIndex];
data[parentIndex] = value;
current = parentIndex;
parentIndex = current/2;
}
}
刪除堆頂元素
刪除堆頂元素的方法是，將堆頂元素刪除，然后將最后一個(gè)元素放到堆頂，這樣就保證了特性1，然后再按住從上往下的順序比較交換元素，以滿足特性2
java代碼實(shí)現(xiàn)
public void removeMax(){
if(count <= 0) return;
data[1] = data[count--];
int current = 1;
while(true){
int maxIndex = current;
if(current *2 <= count && data[current *2] > data[maxIndex]) {
maxIndex = current * 2;
}
if(current *2 + 1 <= count && data[current * 2 + 1] > data[maxIndex]) {
maxIndex = current * 2 + 1;
}
if(maxIndex == current) break;
int temp = data[current];
data[current] = data[maxIndex];
data[maxIndex] = temp;
current = maxIndex;
}
}
有了上述了解之后，接下來我們看看堆最重要的一個(gè)應(yīng)用，堆排序
堆排序可以分成兩步：
1. 建堆
我們先來分析一下原始數(shù)據(jù)，剛開始數(shù)據(jù)是無序的，但其中葉子節(jié)點(diǎn)其實(shí)已經(jīng)是“有序”的了，即其滿足堆的定義，大于它所有的子節(jié)點(diǎn)，因?yàn)樗鼈儧]有子節(jié)點(diǎn)；所有我們只需要對非葉子節(jié)點(diǎn)進(jìn)行排序即可，這里可以宣傳從上往下heapify的方法來建堆
java代碼實(shí)現(xiàn)如下：
public static void buildHeap(int[] array, int n){
if(array == null || array.length < 2) return;
for(int i = n/2; i >= 1; i--){
heapify(array, n, i);
}
}
private static void heapify(int[] array, int n, int i) {
while(true){
int maxIndex = i;
if(i * 2 <= n && array[i*2] > array[maxIndex]) {
maxIndex = i * 2;
}
if(i*2 + 1 <= n && array[i*2+1] > array[maxIndex]){
maxIndex = i * 2 + 1;
}
if(maxIndex == i) break;
swap(array, i, maxIndex);
i = maxIndex;
}
}
private static void swap(int[] array, int i, int maxIndex) {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
2. 排序
堆建成之后，我們能確定的是第一個(gè)元素就是最大元素了（或者最小元素），其他元素的順序無法確定，所以我們此時(shí)將第一個(gè)元素和最好一個(gè)個(gè)元素互換，堆大小減一，此時(shí)給我沒刪除操作類似了，只需要再次堆話就可以得到第二大數(shù)據(jù)，依次類推可以對整個(gè)數(shù)組排序
java 代碼實(shí)現(xiàn)
public static void sort(int[] array, int n){
buildHeap(array, n);
if(array == null || array.length < 2) return;
while(n > 1){
swap(array, 1, n--);
heapify(array, n, 1);
}
}
堆的應(yīng)用場景
- 優(yōu)先級隊(duì)列
java 中的PriorityQueue 就是用堆實(shí)現(xiàn)的 - 取數(shù)組中TopK的數(shù)據(jù)
假如我們要取一組數(shù)據(jù)中的top 5,那么我們只需要維護(hù)一個(gè)5個(gè)元素大小的小根堆，當(dāng)有數(shù)據(jù)加進(jìn)來時(shí)只需要和堆頂元素做比較，如果比堆頂元素小直接忽略，如果比堆頂元素大，則置換調(diào)堆頂元素，然后做heapify.這樣每次加數(shù)據(jù)都只需要和堆頂元素做比較 -
利用堆求中位數(shù)
對應(yīng)靜態(tài)數(shù)據(jù)我們可以直接用快排找；對于動(dòng)態(tài)變化的數(shù)據(jù)，用堆就比較合適了，這里需要維護(hù)兩個(gè)堆，一個(gè)大根堆，一個(gè)小根堆；大根堆里面存儲前一半小數(shù)據(jù)，小根堆里面存儲后一半大數(shù)據(jù)。每次插入數(shù)據(jù)的時(shí)候和大根堆堆頂元素比較，小于則放入大根堆，大于則放入小根堆，放完之后為了保證大根堆的堆頂就是中位數(shù)，我們可能需要在兩個(gè)堆之間移動(dòng)一下數(shù)據(jù)；
image.png
