資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

1.二叉樹的概念

1.一棵二叉樹是結點的一個有限集合該集合:

2.或者為空，由一個根節點加上兩棵别稱為左子樹和右子樹的二叉樹組成

由圖可知二叉樹的每個節點的度==不超過2==
二叉樹分為左子樹和右子樹，==二叉樹是有序樹==
任意的二叉樹都由基本的幾個情況複合而來

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

2.特殊二叉樹

滿二叉樹：一個二叉樹，如果==每個層的結點數==達到最大值那麼這就是一個滿二叉樹。
也就是說如果一個樹k層的話，這個樹有2^k^-1個結點數，那麼這就是滿二叉樹

完全二叉樹：完全二叉樹是效率很高的資料結構，完全二叉樹是由滿二叉樹而引出來的。對于深度為K 的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編号從1至n的結點一一對應時稱之為完全二叉樹。==滿二叉樹是一種特殊的完全二叉樹==
完全二叉樹的節點都要是連續的！

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

這就是一顆完全二叉樹！每個結點都是聯系的！

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

這就不是一顆完全二叉樹因為結點不連續！

完全二叉樹是錢k-1層是滿的，最後K層不一定滿是以節點的數量為==[2^k-1^,2^k^-1]==

關于二叉樹的層數，有的是從0開始，有的是從1開始，一般都是從1開始，這樣子空樹就規定為0，若是從0開始，則空樹就要規定為-1。

3.二叉樹的性質

若規定根節點的層數為1，則一棵非空二叉樹的第i層上最多有2^(i-1)^個結點.
若規定根節點的層數為1，則深度為h的二叉樹的最大結點數是 2^h^-1
對任何一棵二叉樹, 如果度為0其葉結點個數為n~0~, 度為2的分支結點個數為n~2~,則有 n~0~＝ n~2~＋1
這是一個很重要的性質！對于二叉樹而言葉子節點的個數永遠比度為2的節點的個數+1.
若規定根節點的層數為1，具有n個結點的滿二叉樹的深度，==h= log~2~(n+1)==. (ps：是log以2 為底，n+1為對數)
對于具有n個結點的完全二叉樹，如果按照從上至下從左至右的數組順序對所有節點從0開始編号，則對于序号為i的結點有：
1. 若i>0，i位置節點的雙親序号：(i-1)/2；i=0，i為根節點編号，無雙親節點
2. 2i+1<n，左孩子的序号為2i+1，若2i+1>=n，則說明無左孩子
  2i+1>= n意味着超過了最大的序号數
3. 2i+2<n，右孩子的序号為2i+2，若2i+2>=n，則說明無右孩子

堆的概念：

如果有一個關鍵碼的集合K = {k~0~ ，k~1~ ，k~2~ ，k~3,~…， k~n-1~}，把它的所有元素按==完全二叉樹==的順序存儲方式存儲在一個==一維數組==中，并滿足：K~i~ <= K~2i+1~且 K~i~<=K~2i+2~ (K~i~ >=K~2i+1~ 且 K~i~>= K~2i+2~) i = 0，1， 2…，則稱為小堆(或大堆)。将==根節點最大的堆叫做最大堆或大根堆，根節點最小的堆叫做最小堆或小根堆==。

1.堆的性質

堆中的某個節點的值總是不大于或者不小于父節點的值（大堆或者小堆）
堆總是一顆完全二叉樹

堆的難點!

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

堆的邏輯結構和堆的實體存儲結構是完全不一樣的！操作的是數組，但是表示出來的卻是二叉樹！

2.堆的結構

typedef int  HPdataType;
typedef struct Heap
{
    HPdataType* data;//堆的存儲結構本質就是一個數組
    int size;//用來表示數組内的元素的多少
    int capacity;//用來表示數組的記憶體大小！
}//堆的結構與順序表相同，但是因為操作方式的不同導緻了堆與順序表完全不同的性質！

堆的建立後面進行闡述，因為堆的建立有兩種方式一種是将一個非堆的數組通過調整變成堆，另一種是通過數組插入的方式獲得一個堆，兩種的本質其實都是相同的！

3.堆的初始化

void HeapIint(Heap* php)//堆剛建立的堆進行初始化！
{
    php->data = NULL;
    php->size = php->capacity = 0;
}

4.堆的插入

//堆插入的重點在于在插入後仍要保持堆的基本結構！保持大堆或者小堆！
//思路是先插入到最後面，然後進行向上調整算法
typedef int  HPdataType;
void AdjustUp(HPdataType* a,int child);

typedef struct Heap
{
    HPdataType* data;
    int size;
    int capacity;
}
void HeapPush(Heap* php,HPdataType x)
{
    assert(php);
    if(php->size == php->capacity)//先檢查容量是否足夠！不夠則進行擴容
    {
        int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
        HPdataType temp* = (HpdataType*)realloc(php->data,
        sizeof(HPdataType)*newcapacity);
        
        if(temp == NULL)//檢查是否擴容成功！
        {
            perror("realloc fail!");
            return;
        }
        php->data = temp;
        php->capacity = newcapacity;
    }
    php->data[php->size++] = x;
    AdjustUp(php->a,php->size-1);
    //插入尾部，現在開始進行向上調整！将其調整為堆！
    //傳過去最後一個插入的資料的位置和數組
    
}

void swap(HPdataType* x,HPdataType* y)
{
    HPdataType temp = *x;
    *x = *y;
    *y = temp;
}

void AdjustUp(HPdataType* a,int child)
{
    int parent = (child-1) / 2;//找到父節點
    
    while(child > 0)//child不用等于0因為，到0這個位置上面也就沒有父節點了
    {
        if(a[child] > a[parent])//這裡以大堆為例！
        {   swap(&a[child],&a[parent]);
            child = parent;
            parent = (child -1)/2;
        }
        else
        {
            break;//遇到比child大的那麼久跳出循環
        }
    }
    //這裡如果使用parent>0，那麼因為子節點還在下一個位置，則無法調整根節點
    //如果是parent>=0 因為parent =（0-1）/2 仍然為0，則就會出現死循環！
    
}
//向上調整算法的核心是對比父節點和子節點，如果是大堆，那麼子節點大于父節點那麼就進行互換位置
//如果是小堆那麼則相反過來

向上調整算法的時間複雜度

為了友善計算我們以h層的滿二叉樹為例:

總結點數 N = 2^h^-1;

則 h = log~2~(N+1) ≈ logN;

是以向上調整算法的時間複雜度為logN。

5.堆的建立

從上面的堆的插入可以看出如果我們将第一個邏輯結構為完全二叉樹的數組，一個個進行堆的插入到另一個數組中，這樣子就可以建立出一個堆出來！

void HeapCreat(Heap* php,HPdataType* a,int size)
{
    for(int i = 0;i < size;i++)
    {
        HeapPush(php->data,a[i]);
    }
}

但是如果是這樣的話有點浪費空間，如果我們将數組的值一個個進行向上調整算法，從第一個到最後一個，那麼就可以直接将一個數組變成堆！

typedef int  HPdataType;
typedef struct Heap
{
    HPdataType* data;
    int size;
    int capacity;
}

HPdataTpye a[] = {10,2,6,8,1,6,87,12,68,44};
void void HeapCreat(HPdataType* a,int size)
{
    for(int i = 0;i<size;i++)
    {
        AdjustUp(a,i);
    }
}

6.堆的判空

bool HeapEmpty(Heap* php)
{
    return php->size == 0 ? ture : false;
}

7.取堆頂的值！

int HeapTop(Heap* php)
{
    assert(php);
    assert(!eapEmpty(php));
    return php->data[0];
}

8.堆的銷毀

void HeapDestroy(Heap* php)
{
    php->size = 0;
    php->capacity = 0;
    free(php->data);
    php->a = NULL;//防止出野指針
}

9.堆的删除

==堆的删除也與堆的插入一樣要删除後仍保持堆的結構！==

删除的難點在于，如何找到次大/次小的結點，然後将其移動到根節點的位置！

是以堆删除的真正意義在于找打次大/次小節點！

思路:将堆的根結點與最後一個節點互換位置，删除最後一個節點，然後将放在根節點，當做是一個新插入的節點，進行向下調整，最後重新獲得一個新的堆！

向下調整算法的使用前提：==左右子樹必須同時都是大(小)堆==,

typedef int  HPdataType;
typedef struct Heap
{
    HPdataType* data;
    int size;
    int capacity;
}
void AdjustDown(HPdataType* a,int size);

void swap(HPdataType* x,HPdataType* y)
{
    HPdataType temp = *x;
    *x = *y;
    *y = temp;
}

void HeapPop(Heap* php)
{
    assert(php);
    assert(!Heapempty(php));//判斷不是空堆！
    swap(&php->data[0],&php->data[php->size-1]);
    php->size--;//删除最後一個值
    
    AdjustDown(php->data,0,php->size);//進行向下調整！
}

void AdjustDown(HPdataType* a,int parent,int size)
{
    int child = parent*2+1;//預設是左孩子
    
    while(child < size)//不可用parent<size,因為這樣子會出現越界通路！
    {
        if(child +1 < size && a[child] < a[child+1])//這裡仍然以大堆為例，首先找到最大的那個孩子
        {
            child++;
        }
        if(a[parent] < a[child])//比孩子還要小，進行互換
        {
            swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

我們此時又學習到了另一個調整算法，那麼既然可用向上調整算法建堆，那麼我們是否可用使用向下調整算法建堆呢？答案是可行的！但是這兩種算法之間是否存在什麼差別呢？那麼就讓我們先來了解一下建堆的時間複雜度吧！

10.建堆的時間複雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹，此處為了簡化使用滿二叉樹來證明(時間複雜度本來看的就是近似值，多幾個節點不影響最終結果)：

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

而且我們可用看出假設假設樹的高度為h，那麼最後一層就會有2^h-1^個節點，而前h-1層的節點總數為

2^0^+2^1^+2^2^+.....+2^h-2^ = 2^h-1^-1

我們可以看出最後一層的節點數占了總節點數的1/2！

這個時候我們可以來看一下向下調整算法來建堆的代碼

typedef int  HPdataType;
typedef struct Heap
{
    HPdataType* data;
    int size;
    int capacity;
}
void AdjustDown(HPdataType* a,int parent,int size)
{
    int child = parent*2+1;
    
    while(child < size)
    {
        if(child +1 < size && a[child] < a[child+1])
        {
            child++;
        }
        if(a[parent] < a[child])
        {
            swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}
//這個建堆方法要求從最後一個非葉子節點開始！
void HeapCreat(HPdataType* a,int parent,int size)
{
    for(int i = (size-1-1)/2;i>=0;i--)//size-1是最後一個節點的位置,(size-1-1)/2是求出該節點的父節點
    {
        AdjustDown(a,i,size);
    }
}

相比向上調整建堆發我們可以發現，因為向下調整建堆法是從最後一個非葉子節點開始調整的！而向上調整算法是從第一個到最後一個節點。也就意味着向下調整算法的循環次數在滿二叉樹的情況下可以比向上調整算法建堆幾乎少了一半的循環次數！具有更優秀的時間複雜度！向下調整是越多越快！向上調整是越多越慢！

是以我們建堆一般推薦使用向下調整算法！

11.堆的應用

1.堆排序

堆排序就是使用堆的思想來進行排序。
分為兩步

第一步建堆

升序：建大堆

降序：建小堆

為什麼要降序建大堆呢？我們一般的想法不是，将小的放在前面嗎？那不是應該是小堆嗎？

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

由圖我們可以看出來，當我們把最小的找到時候，剩下的數組父子關系已經全亂了！

如果要繼續使用它找到次小的，我們就得重建立堆！這樣是十分的麻煩的！

這樣算起來的時間複雜度為n+(n-1)+.....+1 = n+(n^2^-n)/2

則==時間複雜度為O(N^2^)==

但是如果使用的是大堆：

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

我們先将最後一個與堆頂交換，然後将數組的範圍縮小，因為左右的父子關系都是不變的，是以我們可以使用向下調整算法，将第一個到倒數第二個位置（右圖中4的位置）範圍開始進行向下調整算法，從新找到次大的放在堆頂，然後繼續上一步的過程！這我們就完成了升序！

這樣計算log(n)+log(n-1)+......log(1)

時間複雜度為 ==O(N*logN)==，明顯優于小堆算法！

是以就是第二步利用堆删除思想來進行排序！

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

//代碼示範
typedef int HPdataType;

typedef struct Heap
{
    HPdataType* data;
    int size;
    int capacity;
}
void AdjustDown(HPdataType* a,int parent,int size)
{
    int child = parent*2+1;
    
    while(child < size)
    {
        if(child +1 < size && a[child] < a[child+1])
        {
            child++;
        }
        if(a[parent] < a[child])
        {
            swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}
void swap(HPdataType* x,HPdataType* y)
{
    HPdataType temp = *x;
    *x = *y;
    *y = temp;
}
int main()
{
    HPdataType a[] = {1,4,19,15,7,34,65,25,27,8};
    
    int size = sizeof(a)/sizeof(a[0]);
    for(int i = (size-2)/2;i>=0;i--)//i>0的話無法調整到頂部！
    {
        AdjustDown(a,i,size);
    }//完成建堆
    for(int i = 0;i<size;i++)
    {
        swap(&a[0],&a[size-1-i]);//為什麼要-i呢，因為把該堆最大（小）的放在最後面，然後就不要動他，開始放次大（小）
        AdjustDown(a,0,size-i);//然後開始進行調整！
    }    
    return 0;
}

2.topk問題

TOP-K問題：即求資料結合中前K個最大的元素或者最小的元素，一般情況下資料量都比較大。比如：專業前10名、世界500強、富豪榜、遊戲中前100的活躍玩家等。

一般我們看到這種問題的時候，我們可能會立刻想到排序！但是如果資料量非常大，排序就不太可取了(可能資料都不能一下子全部加載到記憶體中)。最佳的方式就是用堆來解決，基本思路如下：

先建堆
topk和堆排序的有點不一樣
- 找最大的前k個，排小堆
- 找最小的前k個，排大堆

//代碼示範
void AdjustDown(HPdataType* a,int parent,int size)//這是小堆的向下調整
{
    int child = parent*2+1;

    while(child < size)
    {
        if(child +1 < size && a[child] > a[child+1])
        {
            child++;
        }
        if(a[parent] > a[child])
        {
            swap(&a[parent],&a[child]);
            parent = child;
            child = parent*2+1;
        }
        else
        {
            break;
        }
    }
}
void PrintTopK(int* a, int n, int k)//
{
    int* maxheap;
    int* temp = (int*)malloc(sizeof(int)*k);
    if(temp == NULL)
    {
        perror("perror fail");
        return;
    }
    for(int i = 1;i<=k;i++)
    {
        maxheap[i] = a[i];
    }
    for(int i = (k-2)/2;i>=0;i++)
    {
        AdjustDown(maxheap,i,k);
    }//建堆

    for(int i = k;i<n;i++)
    {
        if(maxheap[0] < a[i])
        {
            maxheap[0] = a[i];
            AdjustDown(maxheap,0,k);

        }
    }

    free(maxheap);

}
void TestTopk()
{
 int n = 10000;
 int* a = (int*)malloc(sizeof(int)*n);
 srand(time(0));
 for (size_t i = 0; i < n; ++i)
 {
 a[i] = rand() % 1000000;
 }
 a[5] = 1000000 + 1;
 a[1231] = 1000000 + 2;
 a[531] = 1000000 + 3;
 a[5121] = 1000000 + 4;
 a[115] = 1000000 + 5;
 a[2335] = 1000000 + 6;
 a[9999] = 1000000 + 7;
 a[76] = 1000000 + 8;
 a[423] = 1000000 + 9;
 a[3144] = 1000000 + 10;
 PrintTopK(a, n, 10);
}

//當然其實不止上面一種寫法
void PrintTopK2(int* a, int n, int k)
{
	HP b;
	HeapIint(&b);
	HeapCreat(&b, a, k);

	for (int i = k; i < n; i++)
	{
		if (b.a[0]< a[i])
		{
			b.a[0] = a[i];
			AdjustDown(b.a, 0, k);
		}
	}
	HeapPrint(&b);
	HeapDestroy(&b);
}


void PrintTopK3(int* a, int n, int k)
{
	for (int i = 0; i < k; i++)
	{
		AdjustDown(a, i, k);
	}
	for (int i = k; i < n; i++)
	{
		if (a[0] < a[i])
		{
			a[0] = a[i];
			AdjustDown(a, 0, k);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", a[i]);
	}

}

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

1.二叉樹的概念

2.特殊二叉樹

3.二叉樹的性質

堆的概念：

1.堆的性質

堆的難點!

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

2.堆的結構

3.堆的初始化

4.堆的插入

向上調整算法的時間複雜度

5.堆的建立

從上面的堆的插入可以看出如果我們将第一個邏輯結構為完全二叉樹的數組，一個個進行堆的插入到另一個數組中，這樣子就可以建立出一個堆出來！

6.堆的判空

7.取堆頂的值！

8.堆的銷毀

9.堆的删除

10.建堆的時間複雜度

11.堆的應用

1.堆排序

分為兩步

2.topk問題

繼續閱讀

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[Linux] diff 查找檔案的異同

[轉]ISUP信令的IAM消息詳細内容

c++ 比對相鄰元素相等的元素（adjacent_find）

DateTimePicker 控件的格式設定

C++數組引用C++數組引用

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

[C++學習曆程]基礎部分 C++中的函數學習

使用遞減運算符在循環中按遞減順序列印10到0之間的整數

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

指針，常量和類型别名

VS C++常見問題集錦1.在Vs中編C出現這兩個錯誤是什麼原因？錯誤1：error LNK2005: _main 已經在 *** 中定義

Linux裝置模型（中）之上層容器

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

1.二叉樹的概念

2.特殊二叉樹

3.二叉樹的性質

堆的概念：

1.堆的性質

堆的難點! 資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算

2.堆的結構

3.堆的初始化

4.堆的插入

向上調整算法的時間複雜度

5.堆的建立

從上面的堆的插入可以看出如果我們将第一個邏輯結構為完全二叉樹的數組，一個個進行堆的插入到另一個數組中，這樣子就可以建立出一個堆出來！

6.堆的判空

7.取堆頂的值！

8.堆的銷毀

9.堆的删除

10.建堆的時間複雜度

11.堆的應用

1.堆排序

分為兩步

2.topk問題

繼續閱讀

堆的難點!

資料結構【C語言版】六千字長文帶你了解！堆增删查改，應用，及其時間複雜度的計算