[数据结构]堆的基本操作

堆(heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

1.堆总是一棵完全二叉树。

2.堆中某个节点的值总是不大于或不小于其父节点的值。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。

本次操作具体以小根堆为例进行演示。

堆的存储

一般采用树组存储,i结点的父结点下标为( i - 1 ) / 2。左子树的下标为2 i + 1,右子树的下标为2 i + 2。

堆的操作

堆的插入

每次插入都是将新数据放在数组最后。可以发现从这个新数据的父结点到根结点必然为一个有序的数列,现在的任务是将这个新数据插入到这个有序数据中——这就类似于直接插入排序中将一个数据并入到有序区间中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//  新加入i结点  其父结点为(i - 1) / 2  
void MinHeapFixup(int a[], int i)
{
int j, temp;

temp = a[i];
j = (i - 1) / 2; //父结点
while (j >= 0 && i != 0)
{
if (a[j] <= temp)
break;

a[i] = a[j]; //把较大的子结点往下移动,替换它的子结点
i = j;
j = (i - 1) / 2;
}
a[i] = temp;

插入时

1
2
3
4
5
void MinHeapAddNumber(int a[], int n, int nNum)  
{
a[n] = nNum;
MinHeapFixup(a, n);
}

堆的删除

堆中每次都只能删除根结点,即第0个数据。为了便于重建堆,实际的操作是将最后一个数据的值赋给根结点,然后再从根结点开始进行一次从上向下的调整。调整时先在左右儿子结点中找最小的,如果父结点比这个最小的子结点还小说明不需要调整了,反之将父结点和它交换后再考虑后面的结点。相当于从根结点将一个数据的“下沉”过程。

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
//  从i节点开始调整,n为节点总数 从0开始计算 i节点的子节点为 2*i+1, 2*i+2  
void MinHeapFixdown(int a[], int i, int n)
{
int j, temp;

temp = a[i];
j = 2 * i + 1;
while (j < n)
{
if (j + 1 < n && a[j + 1] < a[j]) //在左右孩子中找最小的
j++;

if (a[j] >= temp)
break;

a[i] = a[j]; //把较小的子结点往上移动,替换它的父结点
i = j;
j = 2 * i + 1;
}
a[i] = temp;
}
//在最小堆中删除数
void MinHeapDeleteNumber(int a[], int n)
{
Swap(a[0], a[n - 1]);
MinHeapFixdown(a, 0, n - 1);
}

构建堆

有了堆的插入和删除后,再考虑下如何对一个数据进行堆化操作。

1
2
3
4
5
6
//建立最小堆  
void MakeMinHeap(int a[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
MinHeapFixdown(a, i, n);
}

堆排序

首先可以看到堆建好之后堆中第0个数据是堆中最小的数据。取出这个数据再执行下堆的删除操作。这样堆中第0个数据又是堆中最小的数据,重复上述步骤直至堆中只有一个数据时就直接取出这个数据。

由于堆也是用数组模拟的,故堆化数组后,第一次将A[0]与A[n - 1]交换,再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n – 2]交换,再对A[0…n - 3]重新恢复堆,重复这样的操作直到A[0]与A[1]交换。由于每次都是将最小的数据并入到后面的有序区间,故操作完成后整个数组就有序了。

1
2
3
4
5
6
7
8
void MinheapsortTodescendarray(int a[], int n)  
{
for (int i = n - 1; i >= 1; i--)
{
Swap(a[i], a[0]);
MinHeapFixdown(a, 0, i);
}
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!