什麼是二叉堆？

二叉堆是一種特殊的堆。具有如下的特性：

具有完全二叉樹的特性。
堆中的任何一個父節點的值都大於等於它左右孩子節點的值(最大堆)，或者都小於等於它左右孩子節點的值（最小堆）。

這個為最大堆：

這個為最小堆：

我們把二叉堆的根節點稱之為堆頂。根據二叉堆的特性，堆頂要嘛是整個堆中的最大元素，要嘛是最小元素。

不過這裡需要注意的是，在二叉堆這種結構中，對於刪除一個節點，我們一般刪的是根節點。

假設"第一個元素"在數組中的索引為 0 的話，則父節點和子節點的位置關係如下：

索引為i的左孩子的索引是 (2*i+1);
索引為i的右孩子的索引是 (2*i+2);
索引為i的父結點的索引是 floor((i-1)/2);

假設"第一個元素"在數組中的索引為 1 的話，則父節點和子節點的位置關係如下：

索引為i的左孩子的索引是 (2*i);
索引為i的右孩子的索引是 (2*i+1);
索引為i的父結點的索引是 floor(i/2);

二叉堆的圖文解析

在前面，我們已經了解到："最大堆"和"最小堆"是對稱關係。這也意味著，了解其中之一即可。本節的圖文解析是以"最大堆"來進行介紹的。

二叉堆的核心是"添加節點"和"刪除節點"，理解這兩個算法，二叉堆也就基本掌握了。下面對它們進行介紹。

1. 添加

假設在最大堆[90,80,70,60,40,30,20,10,50]種添加85，需要執行的步驟如下：

如上圖所示，當向最大堆中添加數據時：先將數據加入到最大堆的最後，然後儘可能把這個元素往上挪，直到挪不動為止！

將85添加到[90,80,70,60,40,30,20,10,50]中後，最大堆變成了[90,85,70,60,80,30,20,10,50,40]。

最大堆的插入代碼(C語言)

/*
 * 最大堆的向上調整算法(從start開始向上直到0，調整堆)
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被上調節點的起始位置(一般為數組中最後一個元素的索引)
 */
static void maxheap_filterup(int start)
{
 int c = start; // 當前節點(current)的位置
 int p = (c-1)/2; // 父(parent)結點的位置 
 int tmp = m_heap[c]; // 當前節點(current)的大小
 while(c > 0)
 {
 if(m_heap[p] >= tmp)
 break;
 else
 {
 m_heap[c] = m_heap[p];
 c = p;
 p = (p-1)/2; 
 } 
 }
 m_heap[c] = tmp;
}
 
/* 
 * 將data插入到二叉堆中
 *
 * 返回值：
 * 0，表示成功
 * -1，表示失敗
 */
int maxheap_insert(int data)
{
 // 如果"堆"已滿，則返回
 if(m_size == m_capacity)
 return -1;
 
 m_heap[m_size] = data; // 將"數組"插在表尾
 maxheap_filterup(m_size); // 向上調整堆
 m_size++; // 堆的實際容量+1
 return 0;
}

maxheap_insert(data)的作用：將數據data添加到最大堆中。

當堆已滿的時候，添加失敗；否則data添加到最大堆的末尾。然後通過上調算法重新調整數組，使之重新成為最大堆。

2. 刪除

假設從最大堆[90,85,70,60,80,30,20,10,50,40]中刪除90，需要執行的步驟如下：

從[90,85,70,60,80,30,20,10,50,40]刪除90之後，最大堆變成了[85,80,70,60,40,30,20,10,50]。

如上圖所示，當從最大堆中刪除數據時：先刪除該數據，然後用最大堆中最後一個的元素插入這個空位；接著，把這個「空位」儘量往上挪，直到剩餘的數據變成一個最大堆。

注意：考慮從最大堆[90,85,70,60,80,30,20,10,50,40]中刪除60，執行的步驟不能單純的用它的子節點來替換；而必須考慮到"替換後的樹仍然要是最大堆"！

最大堆的刪除代碼(C語言)

/* 
 * 返回data在二叉堆中的索引
 *
 * 返回值：
 * 存在 -- 返回data在數組中的索引
 * 不存在 -- -1
 */
int get_index(int data)
{
 int i=0;
 for(i=0; i if (data==m_heap[i])
 return i;
 return -1;
}
/* 
 * 最大堆的向下調整算法
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被下調節點的起始位置(一般為0，表示從第1個開始)
 * end -- 截至範圍(一般為數組中最後一個元素的索引)
 */
static void maxheap_filterdown(int start, int end)
{
 int c = start; // 當前(current)節點的位置
 int l = 2*c + 1; // 左(left)孩子的位置
 int tmp = m_heap[c]; // 當前(current)節點的大小
 while(l <= end)
 {
 // "l"是左孩子，"l+1"是右孩子
 if(l < end && m_heap[l] < m_heap[l+1])
 l++; // 左右兩孩子中選擇較大者，即m_heap[l+1]
 if(tmp >= m_heap[l])
 break; //調整結束
 else
 {
 m_heap[c] = m_heap[l];
 c = l;
 l = 2*l + 1; 
 } 
 } 
 m_heap[c] = tmp;
}
/*
 * 刪除最大堆中的data
 *
 * 返回值：
 * 0，成功
 * -1，失敗
 */
int maxheap_remove(int data)
{
 int index;
 // 如果"堆"已空，則返回-1
 if(m_size == 0)
 return -1;
 // 獲取data在數組中的索引
 index = get_index(data); 
 if (index==-1)
 return -1;
 m_heap[index] = m_heap[--m_size]; // 用最後元素填補
 maxheap_filterdown(index, m_size-1); // 從index位置開始自上向下調整為最大堆
 return 0;
}

maxheap_remove(data)的作用：從最大堆中刪除數據data。

當堆已經為空的時候，刪除失敗；否則查處data在最大堆數組中的位置。找到之後，先用最後的元素來替換被刪除元素；然後通過下調算法重新調整數組，使之重新成為最大堆。

該"示例的完整代碼"以及"最小堆的相關代碼"，請參考下面的二叉堆的實現。

二叉堆的C實現(完整源碼)

二叉堆的實現同時包含了"最大堆"和"最小堆"，它們是對稱關係；理解一個，另一個就非常容易懂了。

二叉堆(最大堆)的實現文件(max_heap.c)

/**
 * 二叉堆(最大堆)
 *
 * @author skywang
 * @date 2014/03/07
 */
#include 
#include 
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
static int m_heap[30]; // 數據
static int m_capacity=30; // 總的容量
static int m_size=0; // 實際容量(初始化為0)
 
/* 
 * 返回data在二叉堆中的索引
 *
 * 返回值：
 * 存在 -- 返回data在數組中的索引
 * 不存在 -- -1
 */
int get_index(int data)
{
 int i=0;
 for(i=0; i if (data==m_heap[i])
 return i;
 return -1;
}
/* 
 * 最大堆的向下調整算法
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被下調節點的起始位置(一般為0，表示從第1個開始)
 * end -- 截至範圍(一般為數組中最後一個元素的索引)
 */
static void maxheap_filterdown(int start, int end)
{
 int c = start; // 當前(current)節點的位置
 int l = 2*c + 1; // 左(left)孩子的位置
 int tmp = m_heap[c]; // 當前(current)節點的大小
 while(l <= end)
 {
 // "l"是左孩子，"l+1"是右孩子
 if(l < end && m_heap[l] < m_heap[l+1])
 l++; // 左右兩孩子中選擇較大者，即m_heap[l+1]
 if(tmp >= m_heap[l])
 break; //調整結束
 else
 {
 m_heap[c] = m_heap[l];
 c = l;
 l = 2*l + 1; 
 } 
 } 
 m_heap[c] = tmp;
}
/*
 * 刪除最大堆中的data
 *
 * 返回值：
 * 0，成功
 * -1，失敗
 */
int maxheap_remove(int data)
{
 int index;
 // 如果"堆"已空，則返回-1
 if(m_size == 0)
 return -1;
 // 獲取data在數組中的索引
 index = get_index(data); 
 if (index==-1)
 return -1;
 m_heap[index] = m_heap[--m_size]; // 用最後元素填補
 maxheap_filterdown(index, m_size-1); // 從index位置開始自上向下調整為最大堆
 return 0;
}
/*
 * 最大堆的向上調整算法(從start開始向上直到0，調整堆)
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被上調節點的起始位置(一般為數組中最後一個元素的索引)
 */
static void maxheap_filterup(int start)
{
 int c = start; // 當前節點(current)的位置
 int p = (c-1)/2; // 父(parent)結點的位置 
 int tmp = m_heap[c]; // 當前節點(current)的大小
 while(c > 0)
 {
 if(m_heap[p] >= tmp)
 break;
 else
 {
 m_heap[c] = m_heap[p];
 c = p;
 p = (p-1)/2; 
 } 
 }
 m_heap[c] = tmp;
}
 
/* 
 * 將data插入到二叉堆中
 *
 * 返回值：
 * 0，表示成功
 * -1，表示失敗
 */
int maxheap_insert(int data)
{
 // 如果"堆"已滿，則返回
 if(m_size == m_capacity)
 return -1;
 
 m_heap[m_size] = data; // 將"數組"插在表尾
 maxheap_filterup(m_size); // 向上調整堆
 m_size++; // 堆的實際容量+1
 return 0;
}
 
/* 
 * 列印二叉堆
 *
 * 返回值：
 * 0，表示成功
 * -1，表示失敗
 */
void maxheap_print()
{
 int i;
 for (i=0; i printf("%d ", m_heap[i]);
}
 
void main()
{
 int a[] = {10, 40, 30, 60, 90, 70, 20, 50, 80};
 int i, len=LENGTH(a);
 printf("== 依次添加: ");
 for(i=0; i {
 printf("%d ", a[i]);
 maxheap_insert(a[i]);
 }
 printf("\\n== 最 大 堆: ");
 maxheap_print();
 i=85;
 maxheap_insert(i);
 printf("\\n== 添加元素: %d", i);
 printf("\\n== 最 大 堆: ");
 maxheap_print();
 i=90;
 maxheap_remove(i);
 printf("\\n== 刪除元素: %d", i);
 printf("\\n== 最 大 堆: ");
 maxheap_print();
 printf("\\n");
}

二叉堆(最小堆)的實現文件(min_heap.c)

/**
 * 二叉堆(最小堆)
 *
 * @author skywang
 * @date 2014/03/07
 */
#include 
#include 
#define LENGTH(a) ( (sizeof(a)) / (sizeof(a[0])) )
static int m_heap[30];
static int m_capacity=30; // 總的容量
static int m_size=0; // 實際容量(初始化為0)
 
/* 
 * 返回data在二叉堆中的索引
 *
 * 返回值：
 * 存在 -- 返回data在數組中的索引
 * 不存在 -- -1
 */
int get_index(int data)
{
 int i=0;
 for(i=0; i if (data==m_heap[i])
 return i;
 return -1;
}
/* 
 * 最小堆的向下調整算法
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被下調節點的起始位置(一般為0，表示從第1個開始)
 * end -- 截至範圍(一般為數組中最後一個元素的索引)
 */
static void minheap_filterdown(int start, int end)
{
 int c = start; // 當前(current)節點的位置
 int l = 2*c + 1; // 左(left)孩子的位置
 int tmp = m_heap[c]; // 當前(current)節點的大小
 while(l <= end)
 {
 // "l"是左孩子，"l+1"是右孩子
 if(l < end && m_heap[l] > m_heap[l+1])
 l++; // 左右兩孩子中選擇較小者，即m_heap[l+1]
 if(tmp <= m_heap[l])
 break; //調整結束
 else
 {
 m_heap[c] = m_heap[l];
 c = l;
 l = 2*l + 1; 
 } 
 } 
 m_heap[c] = tmp;
}
 
/*
 * 刪除最小堆中的data
 *
 * 返回值：
 * 0，成功
 * -1，失敗
 */
int minheap_remove(int data)
{
 int index;
 // 如果"堆"已空，則返回-1
 if(m_size == 0)
 return -1;
 // 獲取data在數組中的索引
 index = get_index(data); 
 if (index==-1)
 return -1;
 m_heap[index] = m_heap[--m_size]; // 用最後元素填補
 minheap_filterdown(index, m_size-1); // 從index號位置開始自上向下調整為最小堆
 return 0;
}
/*
 * 最小堆的向上調整算法(從start開始向上直到0，調整堆)
 *
 * 註：數組實現的堆中，第N個節點的左孩子的索引值是(2N+1)，右孩子的索引是(2N+2)。
 *
 * 參數說明：
 * start -- 被上調節點的起始位置(一般為數組中最後一個元素的索引)
 */
static void filter_up(int start)
{
 int c = start; // 當前節點(current)的位置
 int p = (c-1)/2; // 父(parent)結點的位置 
 int tmp = m_heap[c]; // 當前節點(current)的大小
 while(c > 0)
 {
 if(m_heap[p] <= tmp)
 break;
 else
 {
 m_heap[c] = m_heap[p];
 c = p;
 p = (p-1)/2; 
 } 
 }
 m_heap[c] = tmp;
}
 
/* 
 * 將data插入到二叉堆中
 *
 * 返回值：
 * 0，表示成功
 * -1，表示失敗
 */
int minheap_insert(int data)
{
 // 如果"堆"已滿，則返回
 if(m_size == m_capacity)
 return -1;
 
 m_heap[m_size] = data; // 將"數組"插在表尾
 filter_up(m_size); // 向上調整堆
 m_size++; // 堆的實際容量+1
 return 0;
}
 
/* 
 * 列印二叉堆
 *
 * 返回值：
 * 0，表示成功
 * -1，表示失敗
 */
void minheap_print()
{
 int i;
 for (i=0; i printf("%d ", m_heap[i]);
}
void main()
{
 int a[] = {80, 40, 30, 60, 90, 70, 10, 50, 20};
 int i, len=LENGTH(a);
 printf("== 依次添加: ");
 for(i=0; i {
 printf("%d ", a[i]);
 minheap_insert(a[i]);
 }
 printf("\\n== 最 小 堆: ");
 minheap_print();
 i=15;
 minheap_insert(i);
 printf("\\n== 添加元素: %d", i);
 printf("\\n== 最 小 堆: ");
 minheap_print();
 i=10;
 minheap_remove(i);
 printf("\\n== 刪除元素: %d", i);
 printf("\\n== 最 小 堆: ");
 minheap_print();
 printf("\\n");
}

二叉堆的C測試程序

測試程序已經包含在相應的實現文件中了，這裡就不再重複說明了。

最大堆(max_heap.c)的運行結果：

== 依次添加: 10 40 30 60 90 70 20 50 80 
== 最 大 堆: 90 80 70 60 40 30 20 10 50 
== 添加元素: 85
== 最 大 堆: 90 85 70 60 80 30 20 10 50 40 
== 刪除元素: 90
== 最 大 堆: 85 80 70 60 40 30 20 10 50

最小堆(min_heap.c)的運行結果：

== 依次添加: 80 40 30 60 90 70 10 50 20 
== 最 小 堆: 10 20 30 50 90 70 40 80 60 
== 添加元素: 15
== 最 小 堆: 10 15 30 50 20 70 40 80 60 90 
== 刪除元素: 10
== 最 小 堆: 15 20 30 50 90 70 40 80 60

數據結構-二叉堆

什麼是二叉堆？

二叉堆的圖文解析

1. 添加

最大堆的插入代碼(C語言)

2. 刪除

最大堆的刪除代碼(C語言)

二叉堆的C實現(完整源碼)

二叉堆(最大堆)的實現文件(max_heap.c)

二叉堆(最小堆)的實現文件(min_heap.c)

二叉堆的C測試程序

swapper_pg_dir的作用

Linux動態頻率調節系統CPUFreq之三：governor

內存管理相關數據結構之pg_data_t

linux內核分析 SLAB原理及實現

Android.bp文件簡介

Android.mk文件LOCAL_SDK_VERSION選項

Android應用程式與SurfaceFlinger服務的關係概述和學習計劃

C++ 20 準備發布，C++ 23 提上議程

分享靠寫代碼賺錢的一些門路

經典中的經典算法，動態規劃(詳細解釋，從入門到實踐，逐步講解)

首次適應算法、最佳適應算法和最差適應算法

網絡流的最大流入門

文件頁和匿名頁

Linux-3.14.12內存管理筆記「夥伴管理算法（4）」

一個簡單、輕量的 Linux 協程實現

歸併排序「從入門到放棄」

USB HOST與 USB OTG的區別及工作原理

排序---堆排序

談談協程那些事

宋寶華：Linux內核編程廣泛使用的前向聲明

算法排序----插入排序法

固件分析--工具、方法技巧淺析（上）

各種頁的意義

Linux-3.14.12內存管理筆記「建立內核頁表（3）」