堆這種資料結構相信大家肯定學過，但是因為在實際工作當中用的比較少而漸漸淡忘了？其實堆用在一些非常經典的場景，這篇文章就來學習一下堆相關内容，最開始我們從堆的底層實作和實際應用舉例開始來了解堆這種資料結構的用途，隻有知道了某個東西的實際用途再來深入學習這樣東西才會更有方向感，然後介紹堆的基本實作，最後用堆來實作找出一篇英文文章中單詞出現次數最多的前k個單詞的這樣的簡單功能。
一、堆底層實作以及實際用途
堆的底層實作
堆是用數組來存儲的，但是我們在對堆進行操作的時候實際是将其看成并建構成一顆完全二叉樹(如果對完全二叉樹不太了解的先去查閱一下資料)，之是以用數組來存儲是因為完全二叉樹比較适合用數組來存儲。用數組來存儲完全二叉樹是非常節省存儲空間的，因為我們不需要像建構二叉樹節點那樣花費記憶體空間來存儲每個節點的左右子節點，可以通過數組下标就直接找到找到一個節點的左右子節點和父節點，我們畫圖來了解一下：
上圖我畫了一個大頂堆和小頂堆，這也是堆的兩種實作方式，通過圖可以很好的了解大頂堆和小頂堆，大頂堆中根節點存儲的是集合中最大的元素，它的左右孩子都小于它，同樣左右子樹也是遵循這樣的規律，小頂堆中根節點存儲的是集合中最小的元素，它的左右孩子都小于它，同樣左右子樹也遵循，堆的操作比如插入删除也正是維護這這樣的一種關系特性。我們結合數組和完全二叉樹來分析一下(注意在用數組實作堆時下标0的位置是沒有用到的)：根節點8的左右孩子6和7所在數組的位置是不是可以直接通過1*2 = 2 和 1*2 + 1 = 3 直接求得？同樣葉子節點3的父節點可以通過6/2 = 3求得？這就是得益于完全二叉樹的特性，那普遍來說某個節點所在位置為 i，那它的父節點所在的數組位置就是 i / 2，左右孩子所在位置分别是 i*2 和 i*2+1（當然這個 i 要考慮臨界邊值問題）。
綜上述分析堆的兩個特性：1）完全二叉樹；2）父親節點的值大于(小于)左右子孩子，同樣左右子樹也遵循。
堆的實際用途
通過學習堆的底層實作之後，我們已經初步了解了堆這種的資料結構，我們根據上面堆的結構特性來分析一下具體的實際用途。
應用1：求TopK的問題，比如我們要擷取Top100的排行榜、熱搜詞等等問題。拿Top熱搜詞來說，大緻的實作思路就是我們先得存儲所有詞的出現次數，然後維護一個大小100的小頂堆，堆頂是目前統計的集合中排行最小的，如果我們新來的詞出現的次數比堆頂還小直接抛棄，如果比堆頂大我們就嘗試插入到堆中，插入的過程中還沒達到最大容量的話就插入，容量達到最大的話就抛棄堆頂元素替換掉堆頂(當然這裡還要進行堆結構的維護，也是後面要将的内容)，周遊到最終小頂堆中儲存的就是所有詞中出現次數最多的前100個熱搜詞。
應用2：求中位數問題，比如我們要知道一個資料集合中，根據某個次元來求中間位置的那個資料，當然相對于靜态資料集合來說可以不用堆就很容易實作，但是對于動态資料集合(資料集合中的資料會頻繁的增加或者減少)使用堆來實作就非常高效，大概思路就是維護兩個堆，一個大頂堆，一個小頂堆。大頂堆中存儲前半部分資料，小頂堆中存儲後半部分資料，且小頂堆中的資料都大于大頂堆中的資料。其實除了求中位數，根據這種實作思路其實還可以實作動态資料集合(可以是任何資料)中任何位置的資料，中位數隻是中間的資料嘛。
除了上面兩個經典的應用，還有很多應用場景，比如将堆用作優先級隊列來合并有序小檔案、高性能的定時器等等。
二、堆的基本實作
上面一節講了堆的底層實作，我們現在來看下堆的基本實作有哪些，具體到有哪些對堆操作的方法，我們下面都以大頂堆來講。
1.堆的插入操作
首先我們要明白的是對堆進行資料的插入和删除都需要滿足堆的兩個特性，對于我們插入新的節點資料，其實就在數組的尾部進行添加，這樣自然會滿足堆所建構的完全二叉樹結構不會被破壞，但是插入新資料後可能就不滿足堆中父親節點和左右孩子的大小關系了，是以插入新的資料後都需要進行堆化(heapify)操作，堆化有兩種形式，一種是從下往上，另一種是從上往下，在插入操作的時候我們很快就能明白肯定是從下往上的，我們具體看下什麼是堆化的過程：
可以看到堆化操作其實很簡單，就是看新增的這個節點和父親節點的大小關系，在大頂堆中如果新增的節點比父親節點大就和父親節點替換位置，然後繼續向上直到小于父親節點或者到達根節點時結束，可以看出在插入新資料經過堆化操作之後就滿足了堆的特性，這也就是堆在插入元素的全部過程，咱麼看代碼，注釋非常清楚啦：
public class Heap {
private int[] nums; // 用數組存儲元素，這個可以是任何資料類型(包括自定義的)，不要有局限性思維！
private int count; // 目前堆中元素數量
private int cap; // 堆的總容量容量
public Heap(int cap){ // 初始化堆的時候指定堆的容量
this.nums = new int[cap + 1]; // 注意這裡要+1，應該知道原因吧？因為0的位置是沒有用到的
this.cap = cap;
this.count = 0;
}
public void insert(int newNum){
if (count >= cap) return; // 如果目前元素個數滿了之後,我們這裡做直接傳回處理
count++; // 先進行将個數添加，這個時候count是不是就指向了目前可以添加元素的位置？細品，細節
nums[count] = newNum;
// 堆化操作
int i = count; // 複制臨時變量，開始進行堆化
while (i/2 > 0 && nums[i] > nums[i/2]){ // 首先目前節點是否有父節點，其次看是否大于父親節點
swap(nums, i, i/2); // 替換位置
i = i/2; // 繼續來
}
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
2.堆的删除操作
我們知道堆分為大頂堆或小堆頂，也就是堆頂元素就是集合中最大或者最小的元素，我們一樣拿大頂堆來說，當我們删除元素的時候就是删除堆頂的最大值的元素，我們看下如果我們粗暴的将堆頂删除然後從左右自孩子中選一個最大的進行填補，直到葉子節點這種方式會有什麼問題，用圖看下：
有沒有發現這種方式最後導緻堆不是一個完全二叉樹了？是以這種删除方式是行不通的，正确的思路就是将數組中的最後一個元素放到堆頂進行覆寫，然後丢掉數組末尾的元素，這個時候還沒結束，你很快很想到次數的堆是不滿足第二特性的，沒錯，這個時候就要進行從上往下的堆化操作，我們一樣用圖來分析整個過程：
同樣根據圖的整個過程發現删除元素也是非常簡單的，兩個大步驟：1）将數組末尾元素替換掉堆頂元素，然後去掉末尾的元素；2）進行從上往下的堆化操作，也就是拿目前堆頂元素與大于本元素的其中最大的那個孩子節點進行位置替換，同樣直到均小于等于左右孩子節點或者到達葉子節點結束。我們來看下代碼實作：
public int removeMax(){ // 大頂堆中也就是删除最大值元素
if (count == 0) return -1; // 如果沒有元素了我們這裡直接做傳回-1處理
int curRemoveMax = nums[1];
nums[1] = nums[count]; // 進行将數組末尾元素替換到堆頂元素
count--; // 進行末尾元素的去除，這裡直接通過count來表明，細品
// 進行堆化操作
heapify(nums, count, 1);
return curRemoveMax;
}
private void heapify(int[] arr, int endIndex, int startIndex){ // 從上往下堆化操作
while (true){
int finalPos = startIndex; // 記錄最終的位置
// 看左孩子是否存在并且是否大于目前元素，如果大于記錄左孩子的位置
if (startIndex * 2 <= endIndex && arr[startIndex] < arr[startIndex * 2]) finalPos = startIndex * 2;
// 看右孩子是否存在并且是否大于目前的最大值，如果大于則記錄有孩子的位置，這裡巧秒的選出左右孩子中最大的那個并且是大于目前節點的位置，細品
if (startIndex * 2 + 1 <= endIndex && arr[finalPos] < arr[startIndex * 2 + 1]) finalPos = startIndex * 2 + 1;
if (finalPos == startIndex) break; // 達到最終的位置，借結束掉
swap(arr, startIndex, finalPos); // 替換位置
startIndex = finalPos; // 更新目前節點的位置
}
}
3.堆的建構
我們上面講了堆的插入和删除，在建構一個堆的過程中我們可以通過循環将所有元素一個個的插入到堆中，最後也就建構成了一個堆，不過我們還可以直接将一個數組原地建構成堆，不需要額外開辟空間然後進行循環插入的方式建構。原地建構堆的思路我們細想一下，是不是可以從數組尾部開始，然後一個一個元素進行從下往上堆化操作，最後到達第一個元素之後我們的數組是不是就成了一個堆？當然這是一種實作方式，其實我們可以有一種更優的方式：從數組後往前找到第一個非葉子節點，根據完全二叉樹第一個非葉子節點的下标位置就是n/2，n/2+1到n都是葉子節點，我們隻需要對n/2及前面的元素進行從上往下堆化即可，細品！我們來看下代碼實作：
public void buildHeap(int[] arr, int curCount){
for (int i = curCount / 2; i >= 1; i--){ // 從第一個非葉子節點開始堆化
heapify(arr, curCount, i);
}
}
private void heapify(int[] arr, int endIndex, int startIndex){ // 從上往下堆化操作
while (true){
int finalPos = startIndex; // 記錄最終的位置
// 看左孩子是否存在并且是否大于目前元素，如果大于記錄左孩子的位置
if (startIndex * 2 <= endIndex && arr[startIndex] < arr[startIndex * 2]) finalPos = startIndex * 2;
// 看右孩子是否存在并且是否大于目前的最大值，如果大于則記錄有孩子的位置，這裡巧秒的選出左右孩子中最大的那個并且是大于目前節點的位置，細品
if (startIndex * 2 + 1 <= endIndex && arr[finalPos] < arr[startIndex * 2 + 1]) finalPos = startIndex * 2 + 1;
if (finalPos == startIndex) break; // 達到最終的位置，借結束掉
swap(arr, startIndex, finalPos); // 替換位置
startIndex = finalPos; // 更新目前節點的位置
}
}
4.堆的排序實作
堆的排序可以有兩種，第一種就是我們可以循環去删除堆頂元素進而得到一個有序的結果集，另外一種方式就是原地排序，我們知道堆用數組存儲的，但是并不是天然有序的，我們進行原地排序就是将這個數組建構成有序的數組，不過就不是堆了，我們看下實作思路：我們同樣對大頂堆進行講解，大頂堆堆頂的元素是最大的，我們可以将數組末尾元素和堆頂元素進行替換，這個時候數組末尾是目前資料集合中最大的元素，然後将新的堆頂元素進行堆化操作，當然此時的結尾節點是數組末尾位置的前一個位置，進行堆化之後再将堆頂和目前數組末尾位置元素進行替換，一直循環直到隻剩下堆頂位置，這樣就實作了原地排序的操作，我就不畫圖了，直接上代碼非常直覺：
public void sort(int[] arr, int curCount){
buildHeap(arr, curCount); // 先将數組進行堆化
int k = curCount;
while (k > 1){
swap(arr, k, 1); // 目前末尾元素和堆頂元素替換
k--; // 更新末尾元素下标
heapify(arr, k, 1); // 将前面數組進行堆化操作
}
}
private void heapify(int[] arr, int endIndex, int startIndex){ // 從上往下堆化操作
while (true){
int finalPos = startIndex; // 記錄最終的位置
// 看左孩子是否存在并且是否大于目前元素，如果大于記錄左孩子的位置
if (startIndex * 2 <= endIndex && arr[startIndex] < arr[startIndex * 2]) finalPos = startIndex * 2;
// 看右孩子是否存在并且是否大于目前的最大值，如果大于則記錄有孩子的位置，這裡巧秒的選出左右孩子中最大的那個并且是大于目前節點的位置，細品
if (startIndex * 2 + 1 <= endIndex && arr[finalPos] < arr[startIndex * 2 + 1]) finalPos = startIndex * 2 + 1;
if (finalPos == startIndex) break; // 達到最終的位置，借結束掉
swap(arr, startIndex, finalPos); // 替換位置
startIndex = finalPos; // 更新目前節點的位置
}
}
上面代碼是片段性的，我在這裡将完整的代碼貼出來友善大家整體閱讀：
public class Heap {
private int[] nums; // 用數組存儲元素，這個可以是任何資料類型(包括自定義的)，不要有局限性思維！
private int count; // 目前堆中元素數量
private int cap; // 堆的總容量容量
public Heap(int cap){ // 初始化堆的時候指定堆的容量
this.nums = new int[cap + 1]; // 注意這裡要+1，應該知道原因吧？因為0的位置是沒有用到的
this.cap = cap;
this.count = 0;
}
public int removeMax(){ // 大頂堆中也就是删除最大值元素
if (count == 0) return -1; // 如果沒有元素了我們這裡直接做傳回-1處理
int curRemoveMax = nums[1];
nums[1] = nums[count]; // 進行将數組末尾元素替換到堆頂元素
count--; // 進行末尾元素的去除，這裡直接通過count來表明，細品
// 進行堆化操作
heapify(nums, count, 1);
return curRemoveMax;
}
public void buildHeap(int[] arr, int curCount){
for (int i = curCount / 2; i >= 1; i--){ // 從第一個非葉子節點開始堆化
heapify(arr, curCount, i);
}
}
public void sort(int[] arr, int curCount){
buildHeap(arr, curCount); // 先将數組進行堆化
int k = curCount;
while (k > 1){
swap(arr, k, 1); // 目前末尾元素和堆頂元素替換
k--; // 更新末尾元素下标
heapify(arr, k, 1); // 将前面數組進行堆化操作
}
}
private void heapify(int[] arr, int endIndex, int startIndex){ // 從上往下堆化操作
while (true){
int finalPos = startIndex; // 記錄最終的位置
// 看左孩子是否存在并且是否大于目前元素，如果大于記錄左孩子的位置
if (startIndex * 2 <= endIndex && arr[startIndex] < arr[startIndex * 2]) finalPos = startIndex * 2;
// 看右孩子是否存在并且是否大于目前的最大值，如果大于則記錄有孩子的位置，這裡巧秒的選出左右孩子中最大的那個并且是大于目前節點的位置，細品
if (startIndex * 2 + 1 <= endIndex && arr[finalPos] < arr[startIndex * 2 + 1]) finalPos = startIndex * 2 + 1;
if (finalPos == startIndex) break; // 達到最終的位置，借結束掉
swap(arr, startIndex, finalPos); // 替換位置
startIndex = finalPos; // 更新目前節點的位置
}
}
public void insert(int newNum){
if (count >= cap) return; // 如果目前元素個數滿了之後,我們這裡做直接傳回處理
count++; // 先進行将個數添加，這個時候count是不是就指向了目前可以添加元素的位置？細品，細節
nums[count] = newNum;
// 堆化操作
int i = count; // 複制臨時變量，開始進行堆化
while (i/2 > 0 && nums[i] > nums[i/2]){ // 首先目前節點是否有父節點，其次看是否大于父親節點
swap(nums, i, i/2); // 替換位置
i = i/2; // 繼續來
}
}
private void swap(int[] arr, int i, int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
到這裡堆涉及到的相關操作已經講解完啦，是不是并不難？我們現在來看下用堆來實作開篇說的簡單的應用：找出一篇英文文章中單詞出現次數最多的前k個單詞的功能。
三、實際例子運用：找出一篇英文文章中單詞出現次數最多的前k個單詞的功能
實作的功能非常簡單，并且忽略了很多邊界值的考慮，大家主要看實作思路即可，如果在實際的工作當中要實作一個這樣的功能要考慮的東西是非常多的，遠遠沒有這麼簡單，比如還需要将英文組詞也納入統計的範圍，這個時候實作的負責度就更高了，大家可以在評論區給出思路，我們來看下我的簡單實作：
public class Top {
/**
* 擷取字元串中出現次數最多的前k個單詞
* @param str 英文串
* @param k 前k個
* @return
*/
private World[] getTopWorld(String str, int k){
if (str.length() < 1) return null;
Map<String, World> record = new HashMap<>(); // 用一個hash散清單來記錄單詞出現的次數，因為散清單這種資料結構查詢時間複雜度為O(1)
int len = str.length();
// 統計每個單詞出現的次數
int curStartIndex = 0; // 記錄每個單詞的起始位置
for (int i = 0; i < len; i++){
char curChar = str.charAt(i);
//if ((curChar - 'a' >= 0 && 'z' - curChar >= 0) || (curChar - 'A' >= 0 && 'Z' - curChar >= 0)) continue;
// 我這裡就考慮這寫分隔符的場景了，實際當中肯定不是這麼來分隔的
if (curChar != ' ' && curChar != ',' && curChar != '.' && curChar != ';' && curChar != ':' && curChar != '!' && curChar != '?') continue;
String curWorld = str.substring(curStartIndex, i).toLowerCase(); // 統一處理成小寫，避免大小寫區分
if (!record.containsKey(curWorld)){
World newWorld = new World(curWorld); // 自定義的類結構，用來儲存單詞和出現的次數
record.put(curWorld, newWorld);
}
record.put(curWorld, record.get(curWorld).incr());
int j = i + 1;
for (; j < len; j++){ // 每個單詞間隔中怕有多個空格或者分隔符，是以維護一下
char nextChar = str.charAt(j);
if (nextChar == ' ' || nextChar == ',' || nextChar == '.' || nextChar == ';' || nextChar == ':' || nextChar == '!' || nextChar == '?') continue;
else break;
}
curStartIndex = j; // 更新下一個單詞的其實位置
i = j - 1; // 這裡要-1因為for循環會進行一次++操作
}
// 利用堆求出現次數最多的前k個
TopWorldHeap heap = new TopWorldHeap(k);
for (Map.Entry<String, World> entry : record.entrySet()){
heap.insert(entry.getValue()); // 進行插入操作，具體看下面的堆的插入實作
}
heap.sort();
return heap.getWorlds();
}
class TopWorldHeap{ // 堆
private World[] worlds; // 堆的實作結構
private int count; // 元素數量
private int cap; // 堆的容量
public TopWorldHeap(int cap){
this.worlds = new World[cap + 1];
this.cap = cap;
this.count = 0;
}
public void insert(World world){
if (count >= cap) { // 如果目前元素個數滿了之後，需要剔除和替換
if (worlds[1].compareTo(world) == 0){ // 小頂堆中堆頂中最小的比目前添加單詞的出現次數少，則替換掉
worlds[1] = world;
heapify(worlds, count, 1); // 進行堆化
}
return;
}
count++;
worlds[count] = world;
int i = count;
while (i/2 > 0 && worlds[i].compareTo(worlds[i/2]) == 0){
swap(worlds, i, i/2);
i = i/2;
}
}
private void heapify(World[] arr, int n, int i){
while (true){
int minPos = i;
if (i*2 <= n && arr[i].compareTo(arr[i*2]) == 1) minPos = i*2;
if (i*2+1 <= n && arr[minPos].compareTo(arr[i*2+1]) == 1) minPos = i*2+1;
if (minPos == i) break;
swap(arr, i, minPos);
i = minPos;
}
}
private void sort(){
int k = count;
while (k > 1){
swap(worlds, 1, k);
k--;
heapify(worlds, k, 1);
}
}
public World[] getWorlds(){
return worlds;
}
private void swap(World[] arr, int i, int j){
World temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
class World implements Comparable<World>{
private String worldName;
private int count; // 初始出現次數均為0
public World(String worldName){
this.worldName = worldName;
this.count = 0;
}
public World incr(){ // 每次次數加1
this.count += 1;
return this;
}
public int getCount(){
return count;
}
public String getWorldName(){
return this.worldName;
}
@Override
public int compareTo(World o) { // 因為是自定義資料類，需要實作大小比較的方法
return this.count >= o.count ? 1 : 0;
}
}
public static void main(String[] args) {
Top topWorld = new Top();
String str = " Since I went to school, the teachers always told us to love our motherland, because we were born here and" +
" its culture was very profound, so that we also should be proud of being part of it. I kept this in " +
"my heart, but one day, I read some negative information from foreign websites. These articles criticized " +
"China and the government. What’s more, there were so many foreigners making bad comments about the Chinese " +
"government, some even to criticized the people. But as our country became stronger and more foreigners came to visit, " +
"they started to change their idea and fell in love with this big old country. I realized that no country was perfect, even " +
"America faced many problems. We have the long history and different culture, which make this country so attractive. " +
"I love my country.";
str = str.trim(); // 整理一下前後的空格
World[] result = topWorld.getTopWorld(str, 10);
for (int i = 1; i < result.length; i++){
System.out.print(result[i].getWorldName() + ":" + result[i].getCount());
System.out.println();
}
}
到這裡堆的相關内容就介紹結束啦，感謝你看到這裡！