導航
1.了解什麼是堆
2.如何建立最小堆，最大堆
3.新增值在堆中如何進行
4.完整的堆排序，升序和降序(兩種方式)
————————————————————————————————————————
1.了解什麼是堆
樹型結構與圖型結構的差别：
看是否有回路，無回路的是樹型，有回路的是圖型
滿二叉樹可以用數組進行存儲,層次周遊順序存儲
設定其中父節點為k，兒子節點(左結點，右節點) 其中左節點 為2*k， 右節點為 2 * k+1
高度為log2^N
其中最典型的應用就是堆(也就是完全二叉樹)
完全二叉樹：
————————————————————————————————————————
2.如何将堆轉化為最小堆，最大堆
有兩層的直接用父結點來比較
三層的應該有倒數一層的右邊節點開始依次往下
代碼如下：（建立最小堆）
//這裡用的是數組的方式存儲堆
void siftdown(int i) //輸入的是從i點往下找
{
int t,flag=0; //flag用來表示無需再進行往下查找
//從i位置開始，判斷是否有左孩子，并且沒有找到最佳位置
while(i*2<=n&&flag==0)
{
if(h[i]>h[i*2]) //比較父節點與左節點的大小
t = i*2;
else
t = i;
if(i*2+1<=n){ //判斷是否存在右孩子
if(h[t]>h[i*2+1]) //比較上一次父節點與左節點的最小值與右孩子大小
t = i*2+1;
}
if(t!=i){ //判斷得到最小值是否為父節點，是的話flag标志1，不是的話交換，繼續往下找
swap(t,i);
i=t;
}
else
flag = 1;
}
}
建立最大堆：隻需要将父節點與左右孩子節點的判大小符号換一下就可以了
————————————————————————————————————————
3.新增值在堆中如何進行
先插入到堆中最後一個位置，在進行與父節點依次比對，找到最合适的位置
整個都用數組儲存
代碼：
//這裡弄得是最小堆
void siftup(int i)
{
int i,flag=0; //flag等于0表示目前子節點比父節點小
if(i==1) return; //如果為根節點直接傳回
while(i!=1&&flag==0)
{
if(h[i]<h[i/2])
swap(i,i/2);
else
flag=1;
i=i/2; //讓子節點等于父節點的位置
}
}
————————————————————————————————————————
4.完整的堆排序，升序和降序
輸入提示：
14
99 5 36 7 22 17 46 12 2 19 25 28 1 92
升序：
#include <stdio.h>
int h[101]; //用來存放堆的數組
int n; //存放堆的個數
void swap(int x,int y)
{
int t;
t = h[x];
h[x] = h[y];
h[y] = t;
}
void siftdown(int i)
{
int t,flag=0; //flag用來表示無需再進行往下查找
//從i位置開始，判斷是否有左孩子，并且沒有找到最佳位置
while(i*2<=n&&flag==0)
{
if(h[i]>h[i*2]) //比較父節點與左節點的大小
t = i*2;
else
t = i;
if(i*2+1<=n){ //判斷是否存在右孩子
if(h[t]>h[i*2+1]) //比較上一次父節點與左節點的最小值與右孩子大小
t = i*2+1;
}
if(t!=i){ //判斷得到最小值是否為父節點，是的話flag标志1，不是的話交換，繼續往下找
swap(t,i);
i=t;
}
else
flag = 1;
}
}
void create()
{
int i;
for(i=n/2;i>=1;i--)
siftdown(i);
}
//用于傳回最小值
int deletemax()
{
int t;
t=h[1];
h[1]=h[n];
n--; //删除一位
siftdown(1); //進行最小堆
return t;
}
int main()
{
int i,num;
scanf("%d",&num);
for(i=1;i<=num;i++)
scanf("%d",&h[i]);
n = num;
//建立最小堆
create();
//删除頂部元素，接着将最後一個元素放入第一個頂點中，輸出删除的元素
for(i=1;i<=num;i++)
printf("%d ",deletemax());
return 0;
}
其中deletemax()函數作用是每次傳回最小值，并且将最後一個值移入到根節點再次進行最小堆，這樣結束時數組中資料已不再是原來的。
若想用這樣的來求降序也是可以的，隻需要建立最大堆就行了，其餘都一樣
另一種方式來求解升序和降序
//之前建立的是最大堆
void headsort()
{
while(n>1)
{
swap(1,n); //将第一個與最後一個進行交換，此時最後一個點為最大值
n--; //下次建立最大堆不帶上最後一個值
siftdown(1); //進行最大堆
}
}
求解升序另一種方法完整：
#include <stdio.h>
int h[101]; //用來存放堆的數組
int n; //存放堆的個數
void swap(int x,int y)
{
int t;
t = h[x];
h[x] = h[y];
h[y] = t;
}
void siftdown(int i)
{
int t,flag=0; //flag用來表示無需再進行往下查找
//從i位置開始，判斷是否有左孩子，并且沒有找到最佳位置
while(i*2<=n&&flag==0)
{
if(h[i]<h[i*2]) //比較父節點與左節點的大小
t = i*2;
else
t = i;
if(i*2+1<=n){ //判斷是否存在右孩子
if(h[t]<h[i*2+1]) //比較上一次父節點與左節點的最小值與右孩子大小
t = i*2+1;
}
if(t!=i){ //判斷得到最小值是否為父節點，是的話flag标志1，不是的話交換，繼續往下找
swap(t,i);
i=t;
}
else
flag = 1;
}
}
//開始建立堆
void create()
{
int i;
for(i=n/2;i>=1;i--)
siftdown(i);
}
//之前建立的是最大堆
void headsort()
{
while(n>1)
{
swap(1,n); //将第一個與最後一個進行交換，此時最後一個點為最大值
n--; //下次建立最大堆不帶上最後一個值
siftdown(1); //進行最大堆
}
}
int main()
{
int i,num;
scanf("%d",&num);
for(i=1;i<=num;i++)
scanf("%d",&h[i]);
n = num;
//建立最小堆
create();
headsort();
//删除頂部元素，接着将最後一個元素放入第一個頂點中，輸出删除的元素
for(i=1;i<=num;i++)
printf("%d ",h[i]);
return 0;
}