堆的定义:认识大根堆和小根堆

对的定义如下：

n个关键字序列a[1...n]称为堆，当且仅当该序列满足：
①a[i]$\ge$a[2i]且a[i] $\ge$ a[2i+1]或
②a[i]$\le$a[2i]且a[i] $\le$ a[2i+1]
可以将该一维数组视为一棵完全二叉树，满足条件①的堆称为大根堆（大顶堆)，大根堆的最大元素存放在根结点,且其任一非根结点的值小于等于其双亲结点值。满足条件②的堆称为小根堆(小顶堆)，小根堆的定义刚好相反，根结点是最小元素。

通俗的来讲，将数组按层排列，每个结点大于其左右孩子结点的值称为大根堆；每个结点小于其左右孩子结点的值称为大根堆
 
  若父结点=i，则左孩子=2i，右孩子=2i+1

堆排序（建立大根堆，从小到大排序）

基本思路

1. 创建初始堆：

2. 将第一步中的根结点与末尾元素进行交换：

3. 将剩余n-1个元素再次进行堆排序，如此往复：

动图

确定最后一个元素的值：

解析图：

完整代码

#include "stdio.h"

typedef int ElemType;


void HeadAjust(ElemType a[], int k, int len) {
    a[0]=a[k];
    for (int i = 2*k; i <= len; i*=2) {
        if (i<len&&a[i]<a[i+1])
            i++;
        if (a[0]>=a[i])
            break;
        else{
            a[k]=a[i];
            k=i;
        }
    }
    a[k]=a[0];
}

void BuildMaxHeap(ElemType a[],int len){
    for (int i = len/2; i > 0; i--) {
        HeadAjust(a,i,len);
    }
}

void HeapSort(ElemType a[],int len){
    BuildMaxHeap(a,len);
    for (int i = len; i > 1; --i) {
        int temp=a[i];
        a[i]=a[1];
        a[1]=temp;
        HeadAjust(a,1,i-1);
    }
}

int main(){
    int n;
    ElemType a[n];
    printf("一共有多少个数需要排序：");
    scanf("%d",&n);
    printf("请输入%d个数：",n);
    for (int i = 1; i <= n; ++i) {
        scanf("%d",&a[i]);
    }
    HeapSort(a,n);
    printf("排序后为：");
    for (int i = 1; i <= n; ++i) {
        printf("%d\t",a[i]);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

运行截图

堆的插入和删除

堆的插入

堆的删除

参考资料

《王道：23数据结构考研复习》