堆的概念
堆的定义
堆可以定义为一颗二叉树,树的节点包含键(每个节点一个键),并且满足下面两个条件:
-
堆的形状要求是一颗完全二叉树,意识就是说,树的每一层都是满的,除了最后一层最右边的元素可能有缺位
-
父母优势要求,就是说每一个节点的键都要大于或等于它子女的键。
堆的判断
下面这个就不是堆,因为不是完全二叉树
下面这个也不是堆,堆的节点比子节点大,4比5小
下面这个是堆
堆的特性
- 一颗n个节点的完全二叉树。它的高度是:[log2n](log以2为底,[]表示向下取整)
- 堆的根总是包含堆的最大元素
- 堆的一个节点以及该节点的子孙也是一个堆
- 可以用数组来实现堆,方法是从上到下,从左到右的方式来记录堆的元素,当有n个元素时,存放在数组的1~n的位置上。此时有:
a 父母节点会在位于数组的前n/2个位置中,而叶子节点将会在占据后n/2个位置
b 在数组中,当父母位置为i时,则子女节点会在2i和2i+1。对于一个位于i的键来说,它的父母节点位于i/2。
堆的构造
构造堆有两种方法,一种是自底向上堆构造;另一种是自定向下堆构造。
自底向上构造
对于堆来说,每一个父母节点的值都要大于子女节点。所以从最后一个父母节点开始,一直到根节点,判断子女节点是否比父母节点的值小,如果大,则将交换父母节点和子女节点的值。
以2,9,7,6,5,8为例:
自顶向下构造
自顶向下堆构造算法的效率低,就是通过把新的键连续插入预先构造好的堆,然后将其值与父母进行比较直至根节点或值小于父母节点时,来构造一个新堆。
比如在下面的堆中插入9:
关于最大堆,最小堆
最大堆就是父节点比子节点大,最小堆就是父母节点比子节点小。
堆排序
堆排序的一般过程
这里以
- 构造堆,堆给定的数组构造堆
- 删除最大键,将最大值和最后一个叶子结点进行交换,然后删除
- 将删除后重新整合,使之成为一个堆,重复2
堆排序样例过程图解
以2,9,7,6,5,8为例
c语言代码
#include <stdio.h>
int num;
void BuildHeap(int A[],int i,int N) //构造堆
{
int c,temp;
for (temp=A[i];2*i<=N;i=c) //temp记录下父母节点的值,c为一个子女节点
{
c=2*i;
if(c<N&& A[c+1]>A[c])//找到最大的子女节点
++c;
if(temp<A[c]) //父母节点值等于子女节点中大的
A[i]=A[c];
else
break;
}
A[i]=temp;//对被交换的子女节点赋值 比如在2 9 8 6 5 7中9和2交换后,2需要和6再进行交换,最后只需要对6最开始的位置赋值2就行
}
void Heapsort(int a[]) //排序
{
int i,temp;
for(i=num/2;i>=1;i--) //从最后一个父母节点开始,知道根节点
{
BuildHeap(a,i,num);
}
for(i=num;i>0;i--) //删除根节点后,重新构造堆
{
temp=a[1];
a[1]=a[i];
a[i]=temp;
BuildHeap(a,1,i-1);
}
}
int main()
{
printf("请输入要排序的数的个数:");
scanf("%d",&num);
int i,a[num+1];
printf("请输入元素:");
for(i=1;i<=num;i++)
scanf("%d",&a[i]);
Heapsort(a);
for(i=1;i<=num;i++)
printf("%d ",a[i]);
}
参考书籍:算法设计与分析基础