二叉樹的順序結構有一個專屬的名稱 堆, "堆" 我熟,他不就是動態開辟的資料都存在那里嗎,他業務那么廣闊還可以用到樹里,其實他們不是同一種東西,同名罷了
堆的一些概念
看看資料結構里面的堆是啥：可以堆理解邏輯結構像是堆上去的，類似金字塔???樹不是也這樣嗎,當然堆其實也是二叉樹，但他是二叉樹的一種變形: 完全二叉樹，是基于順序表結構存盤
如圖：
如上圖那樣存盤如何找他的子節點呢？父節點也沒存他的子節點的指標,那要如何訪問呢？發明出來總是拿來用的,那么來看看大佬是如何想出來的(他有一點 靜態鏈表 的感覺 ）
靜態鏈表簡單描述
- 用陣列實作鏈表,定義結構的時候留一個資料存他后面插入的
下標,可是他還有空間浪費,不想指標練表那么靈活
如何找自己的子節點呢？其中有倆條重要的定義：
公式1: 左孩子=父節點*2+1
公式2: 父節點= (孩子-1)/2
有了這倆個公式之前的疑惑也就煙消云散了,既然可以找到子節點,還可以找到父節點,那么好辦事了,那么就介紹一個比較厲害的東西,堆排
堆排
他是基礎排序中其中之一,是一位優秀的選手,時間復雜度是N*logN (后文推導), 相比冒泡排序(n2)已經是快的沒邊了,廢話不多說,正式介紹一下堆排
堆分為倆在結構 , 大端堆 , 與小端堆 , 這是倆是啥 , 人如其名,大端堆所以的父節點一定比孩子大，小端反之
如圖：
這個時候可能有入要說了，我的完全二叉樹這么不是這樣的，資料都是大小不一的，你這個不會就是自己現象出來的邏輯結構吧，其實不是要變成上圖那個模樣，需要進行倆個操作建堆 排序
建堆
建堆可謂是堆排中最重要的一步，沒有他別的都是后話，因為堆排是在大端堆或者小端堆的基礎進行，如上文所說，一棵樹一般情況下不太會是就是大端 or 小端，甚至不太會是一棵完全二叉樹可他是如何建堆的呢？
下文呢能會覺得有點巧，其實這些都是計算機的先輩研究出來的就像之前的那個三步翻轉法，希爾演算法(之后的博客會介紹)
建立基于上文的倆個公式:
思路：
通過公式1+節點個數，我們就可以找到最后一個帶有葉子的節點
如圖
在比較他子節點的個數是不是小于他或者大于他如果大于就交換，且和孫子節點比直到父親節點小，比子節點大,這個程序有一個專屬的名詞向下調
向下調整
如果說建堆是堆排的核心，那么向下調整就是就是建堆的核心
代碼
void AdJustDown(int* a, int n, int root)//向下調整
{
int parent=root;//父親節點
int child=parent*2+1;//左孩子節點
while(child<n)//如果孩子節點大于節點個數比下去就越界了
{
if(child+1<n&&a[child]<a[child+1])//如果右孩子大于左孩子判斷為真
{
child=child+1;//如果右孩子大就吧左孩子置為右孩子節點
}
if(a[parent]<a[child])//如果孩子大于父親判斷為真
{
Swap(&a[parent],&a[child]);//交換
}
//更新父親，孩子節點
parent=child;
child=parent*2+1;
}
}
建堆代碼
int parent=(n-2)/2;//最后一節點的父親
for(int i= parent;i>=0;i--)//這個就是上文說的巧的代碼，每進一次回圈都會讓這個節點變得有序
{
AdJustDown(a,n,i);
}
運行動圖
請配合上面的代碼食用
排序
排序那么如何排序那？排升序是要 建大堆呢？還是建小堆？那么先看一下如何排序吧，看完就豁然開朗了
排序思想：
尾巴元素和首元素交換在向下調整
代碼：
int end=n-1;//最后一個節點
for(int i =end;i>=0;i--)//控制end，每次迭代end
{
Swap(&a[0],&a[i]);//首元素和尾元素交換
AdJustDown(a,i,0);//向下調整
}
運行動圖
上面這個動圖其實就可以看出排升序要建大堆，為啥呢，那么看建小堆如何走的
動圖演示：
顯然可以看出，建立小堆排的話就是降序
結論：
排升序建大端，排降序建小端
拓展
堆其實是一個陣列，那么他可以和順序表一樣尾插資料嗎？當然可也，那么他如何保持有序呢？？？
向上調整
思想：
在有序的情況下 , 找到父節點和父節點比較如果比父節小 ( 升序的情況 )交換，這是向下調整逆推的一個程序
如圖：
在這個程序中有人看能要問了，他和父節點交換如果左孩子比他小這么辦(升序), 那不會，你想是在有序的情況下，那么父節點一定是比他的孩子要的大
代碼：
void AdjustUp(int *arr,int tmp,int son)//👆調整
{
int father= (son-2)/2;
while(son>0)
{
if(arr[father]>arr[son])
{
Swap(&arr[father],&arr[son]);
son=father;
father=(son-1)/2;
}
else
{
break;
}
}
}
向上調整建堆
既然向下調整可以建堆，那么向上調整可以建嗎？他有點類似尾插
思路：
從頭開始一次拿一個，每次插入都向上調整
圖解：
時間復雜度
上文說堆的時間復雜度是O(Nlog2N)，如何算呢
推導：
勺ò干以看到在排序的時候的是要走N次的，且每次都要向下調整，向下調整如何計算呢，一般算的是最壞的情況，那么就是每一層都要比，那么如何算層數呢，log(節點個數)，因此推匯出來是O(Nlog(N))
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/303027.html
標籤：java
上一篇：小學生四則運算--軟體工程