🐶博主主頁：@??. 一懷明月??

???🔥專欄系列：線性代數(shù)，C初學(xué)者入門訓(xùn)練，題解C，C的使用文章，「初學(xué)」C++，數(shù)據(jù)結(jié)構(gòu)

🔥座右銘：“不要等到什么都沒有了，才下定決心去做”

🚀🚀🚀大家覺不錯的話，就懇求大家點點關(guān)注，點點小愛心，指點指點🚀🚀🚀

目錄

樹

樹的概念

樹的表示

二叉樹

二叉樹概念：

特殊的二叉樹

二叉樹的性質(zhì)

二叉樹的存儲結(jié)構(gòu)

2. 鏈?zhǔn)酱鎯?/p>

堆

二叉樹的順序結(jié)構(gòu)

堆的概念及結(jié)構(gòu)

堆排序?

堆排序的實現(xiàn)

建堆

堆排序

TOPK

---

樹

樹的概念

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，它是由n（n>=0）個有限結(jié)點組成一個具有層次關(guān)系的集合。把它叫做樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，而葉朝下的。

圖1

圖2

節(jié)點的度：一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點的度；如圖2:A的度為6

葉節(jié)點（終端節(jié)點）：度為0的節(jié)點稱為葉節(jié)點；如圖2:B、C、H、I...等為葉節(jié)點

父節(jié)點（雙親節(jié)點）：若一個節(jié)點含有子節(jié)點，則這個節(jié)點稱為其子節(jié)點的父節(jié)點；如圖2:A是B的父節(jié)點

子節(jié)點（孩子節(jié)點）：一個節(jié)點含有的子樹的根節(jié)點稱為該節(jié)點的子節(jié)點；如圖2:B是A的子節(jié)點

兄弟節(jié)點：具有相同父節(jié)點的節(jié)點互稱為兄弟節(jié)點；如圖2:B、C是兄弟節(jié)點

樹的度：一顆樹中，最大的節(jié)點的度稱為樹的度；如圖2:樹的度為6

節(jié)點的層次：從根開始定義起，根為第一層，根的子節(jié)點為第二層，依次類推

樹的高度（樹的深度）：樹中節(jié)點的最大層次；如圖2:樹的高度為4

堂兄弟節(jié)點：雙親在同一層的節(jié)點互為堂兄弟；如圖2:H、I互為堂兄弟節(jié)點

節(jié)點祖先：從根到該節(jié)點所經(jīng)分支上的所有節(jié)點；如圖2；A是所有節(jié)點的祖先

子孫：以某節(jié)點為根的子樹中任一節(jié)點都稱為該節(jié)點的子孫；如圖2:所有節(jié)點都是A的子孫

森林：由m（m>0）棵互不相交的樹的集合稱為森林

樹的表示

樹結(jié)構(gòu)相對線性表就比較復(fù)雜了，要存儲表示起來就比較麻煩了，既然保存值域，也要保存結(jié)點和結(jié)點之間的關(guān)系，實際中樹有很多種表示方式如：雙親表示法，孩子表示法、孩子雙親表示法以及孩子兄弟表示法等。我們這里就簡單的了解其中最常用的孩子兄弟表示法，即左孩子右兄弟表示法。

typedef int DataType;
struct Node
{
struct Node* _firstChild1; // 第一個孩子結(jié)點
struct Node* _pNextBrother; // 指向其下一個兄弟結(jié)點
DataType _data; // 結(jié)點中的數(shù)據(jù)域
};

圖3

樹在實際中的運用：表示文件系統(tǒng)的目錄樹結(jié)構(gòu)

圖4

二叉樹

二叉樹概念：

二叉樹（Binary Tree）是n（n>=0）個結(jié)點的有限集合，該集合或者空集（稱為空二叉樹），或者由一個根節(jié)點和兩顆互不相交的，分別稱為根節(jié)點的左子樹和右子樹的二叉樹組成。

圖5

（1）二叉樹的最大度為2；

（2）每個結(jié)點最多有兩棵子樹；

（3）左子樹和右子樹是有順序的；

（4）即使樹中某結(jié)點只有一顆子樹，也要區(qū)分左右；

注意：對于任意的二叉樹都是由以下幾種情況復(fù)合而成的：

圖6

特殊的二叉樹

1.滿二叉樹：一個二叉樹，如果每一層的節(jié)點數(shù)都達到了最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數(shù)為k，且節(jié)點總數(shù)是2^k-1，則它是滿二叉樹。

2.完全二叉樹：完全二叉樹是效率很高的數(shù)據(jù)結(jié)構(gòu)，完全二叉樹是由滿二叉樹而引出來的。對于深度為k的，有n個節(jié)點的二叉樹，當(dāng)且僅當(dāng)每一個節(jié)點都與深度為k的滿二叉樹中編號從1至n的節(jié)點————對應(yīng)時稱之完全二叉樹。要注意滿二叉樹是一種特殊的完全二叉樹。

?圖7

二叉樹的性質(zhì)

1. 若規(guī)定根節(jié)點的層數(shù)為1，則一棵非空二叉樹的第i層上最多有2^(i-1)個結(jié)點.

2. 若規(guī)定根節(jié)點的層數(shù)為1，則深度為h的二叉樹的最大結(jié)點數(shù)是2^h-1.

3. 對任何一棵二叉樹, 如果度為0其葉結(jié)點個數(shù)為n0, 度為2的分支結(jié)點個數(shù)為 n2,則有n0＝n2+1

4. 若規(guī)定根節(jié)點的層數(shù)為1，具有n個結(jié)點的滿二叉樹的深度，h=log2^(n+1) (是log以2為底，n+1為對數(shù))

5. 對于具有n個結(jié)點的完全二叉樹，如果按照從上至下從左至右的數(shù)組順序?qū)λ泄?jié)點從0開始編號，則對于序號為i的結(jié)點有：

（1. 若i>0，i位置節(jié)點的雙親序號：(i-1)/2；i=0，i為根節(jié)點編號，無雙親節(jié)點

（2. 若2i+1<n，左孩子序號：2i+1，2i+1>=n否則無左孩子

（3. 若2i+2<n，右孩子序號：2i+2，2i+2>=n否則無右孩子

二叉樹的存儲結(jié)構(gòu)

二叉樹一般可以使用兩種結(jié)構(gòu)存儲，一種順序結(jié)構(gòu)，一種鏈?zhǔn)浇Y(jié)構(gòu)。

1.順序存儲

順序結(jié)構(gòu)存儲就是使用數(shù)組來存儲，一般使用數(shù)組只適合表示完全二叉樹，因為不是完全二叉樹會有空間的浪費。而現(xiàn)實中使用中只有堆才會使用數(shù)組來存儲。二叉樹順序存儲在物理上是一個數(shù)組，在邏輯上是一顆二叉樹

圖8

2. 鏈?zhǔn)酱鎯?/h2>

...

堆

二叉樹的順序結(jié)構(gòu)

普通的二叉樹是不適合用數(shù)組來存儲的，因為可能會存在大量的空間浪費。而完全二叉樹更適合使用順序結(jié)構(gòu)存儲?，F(xiàn)實中我們通常把堆(一種二叉樹)使用順序結(jié)構(gòu)的數(shù)組來存儲，需要注意的是這里的堆和操作系統(tǒng)虛擬進程地址空間中的堆是兩回事，一個是數(shù)據(jù)結(jié)構(gòu)，一個是操作系統(tǒng)中管理內(nèi)存的一塊區(qū)域分段

堆的概念及結(jié)構(gòu)

如果有一個關(guān)鍵碼的集合K = {k0,k1,k2,...,k[n-1] }，把它的所有元素按完全二叉樹的順序存儲方式存儲

在一個一維數(shù)組中，并滿足： Ki<=K[2*i+1] 且Ki<=K[2*i+2](Ki>=K[2*i+1] 且Ki>=K[2*i+2]),i=0,1,2...n

則稱為小堆(或大堆)。將根節(jié)點最大的堆叫做最大堆或大根堆，根節(jié)點最小的堆叫做最小堆或小根堆。

堆的性質(zhì)：

堆中某個節(jié)點的值總是不大于或不小于其父節(jié)點的值；

堆總是一棵完全二叉樹

圖9

堆排序?

堆排序是利用堆這種數(shù)據(jù)結(jié)構(gòu)而設(shè)計的一種排序算法，他的時間復(fù)雜度是O(N*logN)相較于冒泡排序（O(N*N)）他的時間效率非常高。

堆排序的實現(xiàn)

1.將無序序列構(gòu)建成一個堆，根據(jù)升序(降序)需求選擇大根堆(小根堆)

2.將堆頂元素與末尾元素交換，將最大元素（最小元素）“沉”到數(shù)組末端

3.重新調(diào)整結(jié)構(gòu)使其滿足堆定義，然后繼續(xù)交換堆頂元素與當(dāng)前末尾元素，反復(fù)執(zhí)行調(diào)整+交換步驟，直到整個序列有序

建堆

建堆有著兩種建堆的方法，向上調(diào)整建堆和向下調(diào)整建堆，不管是建大根堆還是小根堆這兩種方法都可以。

向上調(diào)整：

這里是準(zhǔn)備建小根堆，Swap是交換函數(shù)（交換兩個變量的值），判斷最后一個孩子節(jié)點child的值是否比其父節(jié)點parent的值小，如果child的值比parent的值小，就交換父子節(jié)點的值，然后孩子節(jié)點child的位置移到父節(jié)點parent的位置，父節(jié)點parent移到父節(jié)點的父節(jié)點，然后再次判斷孩子節(jié)點child的值與父節(jié)點parent的值的大小，直到child移到了根節(jié)點，如果child的值比parent的值如果大，就不用交換并且說明本次調(diào)整完成。

void AdjustUP(int* a,int n)
{int child=n-1;int parent=(child-1)/2;while(child>0){if(a[child]<a[parent]){Swap(&a[child], &a[parent]);child=parent;parent=(child-1)/2;}else{break;}}
}

向下調(diào)整：

這里是準(zhǔn)備建小根堆，判斷父節(jié)點parent的值是否比其孩子節(jié)點child（一般父節(jié)點都有兩個孩子節(jié)點，這里的孩子節(jié)點是兩個中較小的那個）的值小，如果child的值比parent的值小，就交換父子節(jié)點的值，然后父節(jié)點parent的位置移到孩子節(jié)點child的位置，孩子節(jié)點child移到孩子節(jié)點的孩子節(jié)點的位置，然后再次判斷孩子節(jié)點child的值與父節(jié)點parent的值的大小，直到child的值大于元素個數(shù)，如果child的值比parent的值如果大，就不用交換并且說明本次調(diào)整完成。

void AdjustDown(int* a,int n,int parent)
{int child=parent*2+1;while(child<n){if(child+1<n&&a[child]>a[child+1]){child++;}if(a[child]<a[parent]){Swap(&a[child], &a[parent]);parent=child;child=parent*2+1;}else{break;}}
}

向上調(diào)整建堆：

?向上建堆是從第二層開始直到第h層，所以其時間復(fù)雜度為O(N*logN)

  for(int i=1;i<n;i++){AdjustUP(a, i);}

向下調(diào)整建堆：

向下建堆是從第h-1層直到第一層，所以其時間復(fù)雜度為O(N)

for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(a, n,i);}

堆排序

由于有兩種建堆方式，向上調(diào)整建堆和向下調(diào)整建堆，所以就有兩種堆排序方式。

HeapSort_UP(向上建堆排序):

//時間復(fù)雜度為O(N*logN)
void HeapSort_UP(int* a,int n)
{//向上建堆是從第二層開始直到第h層，所以其時間復(fù)雜度為O(N*logN)for(int i=1;i<n;i++){AdjustUP(a, i);}int end=n-1;//建堆完成后，需要進行向下調(diào)整其時間復(fù)雜度為O(N*logN)while(end>0){Swap(&a[0], &a[end]);AdjustDown(a, end,0);end--;}
}

HeapSort_Down(向下建堆排序):

//時間復(fù)雜度為N*logN
void HeapSort_Down(int* a,int n)
{//向下建堆是從第h-1層直到第一層，所以其時間復(fù)雜度為O(N)for(int i=(n-1-1)/2;i>=0;i--){AdjustDown(a, n,i);}int end=n-1;//建堆完成后，需要進行向下調(diào)整其時間復(fù)雜度為O(N*logN)while(end>0){Swap(&a[0], &a[end]);AdjustDown(a, end,0);end--;}
}

總結(jié)：向上建堆從第二層開始直到第h層，向下建堆是從第h-1層直到第一層，雖然它們經(jīng)歷的層數(shù)相同，但是向上建堆中第一層不用調(diào)整，向下建堆中第h層不用調(diào)整（h為最后一層），第一層的元素只有一個，第h層元素有2^(h-1)個。所以他們的時間復(fù)雜度不同，向上建堆為O(N*logN)，向下建堆為O(N)，盡量使用向下建堆的方式來實現(xiàn)堆排序。

TOPK

TOP-K問題：即求數(shù)據(jù)結(jié)合中前K個最大的元素或者最小的元素，一般情況下數(shù)據(jù)量都比較大。
比如：專業(yè)前10名、世界500強、富豪榜、游戲中前100的活躍玩家等。
對于Top-K問題，能想到的最簡單直接的方式就是排序，但是：如果數(shù)據(jù)量非常大，排序就不太可取了(可能數(shù)據(jù)都不能一下子全部加載到內(nèi)存中)。最佳的方式就是用堆來解決，基本思路如下：
1. 用數(shù)據(jù)集合中前K個元素來建堆
前k個最大的元素，則建小堆
前k個最小的元素，則建大堆
2. 用剩余的N-K個元素依次與堆頂元素來比較，不滿足則替換堆頂元素,將剩余N-K個元素依次與堆頂元素比完之后，堆中剩余的K個元素就是所求的前K個最小或者最大的元素。

例如：我們這里實現(xiàn)在1000000個數(shù)中找出5個最大的數(shù)，為了方便實現(xiàn)我們使用rand()生成1000000個數(shù)。為了貼近實戰(zhàn)項目，我們會將這1000000個數(shù)據(jù)寫到文件中，然后文件中讀取。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
void Swap(int* e1,int* e2)
{int temp=*e1;*e1=*e2;*e2=temp;
}
void AdjustDown(int* a,int n,int parent)
{int child=parent*2+1;while(child<n){if(child+1<n&&a[child]>a[child+1]){child++;}if(a[child]<a[parent]){Swap(&a[child], &a[parent]);parent=child;child=parent*2+1;}else{break;}}
}
void CreatData(void)
{//system("pwd\n");int n=1000;srand((unsigned int)time(NULL));const char* file="data.txt";FILE* fout=fopen(file, "w");for(int i=0;i<n;i++){int x=rand()%1000000;fprintf(fout, "%d\n",x);}fclose(fout);
}
void PrintTopk(int k)
{const char* file="data.txt";FILE* fin=fopen(file, "r");int* kminheap=(int*)malloc(sizeof(int)*k);for(int i=0;i<k;i++){fscanf(fin,"%d",&kminheap[i]);}//建小堆，for(int i=(k-1-1)/2;i>=0;i--){AdjustDown(kminheap, k, i);}int val=0;while(!feof(fin)){fscanf(fin, "%d",&val);if(val>kminheap[0]){kminheap[0]=val;AdjustDown(kminheap, k, 0);}}for(int i=0;i<k;i++){printf("%d ",kminheap[i]);}
}
int main()
{//CreatData();PrintTopk(5);return 0;
}

?🌸🌸🌸如果大家還有不懂或者建議都可以發(fā)在評論區(qū)，我們共同探討，共同學(xué)習(xí)，共同進步。謝謝大家！ 🌸🌸🌸???