【数据结构与算法】堆与堆排序
目录
- 一.堆的实现
- 1.堆的概念
- 2.堆的代码实现
- 二.堆排序的讲解
一.堆的实现
1.堆的概念
堆是一种数据结构，首先它总是一颗完全二叉树(因为堆适合表示完全二叉树)，在逻辑上堆是一颗完全二叉树，真正实现上是使用数组来实现的。根据不同的规则(任意根节点比左右孩子大或者小)区分出大根堆和小根堆。
上图就是一个大根堆的演示，小根堆则相反。
2.堆的代码实现
堆的底层逻辑就是数组，所以创建堆只需要先创建个数组。接着我们想通过数组建堆，就需要调整数据在数组中的位置。
现在我们假设有一个乱序的数组:
我们要将其调整为大根堆的情况，则需要从第二层左孩子开始向上调整。上图为数据26作为孩子节点大于其父节点15，则26与15 交换
以此类推继续调整右孩子12…逐层向下。最终可以将其调整为一个大根堆:
代码的实现如下:
创建堆结构，初始化与销毁:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}HP;
void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapInit(HP* php)
{
assert(php);
php->a = (HPDataType*)malloc(sizeof(HPDataType) * 4);
if (php->a == NULL)
{
perror("malloc fail");
return;
}
php->capacity = 4;
php->size = 0;
}
void HeapDestroy(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
向堆插入数据后，为了保持堆为大根堆，需要对数据进行调整:
typedef int HPDataType;
void HeapPush(HP* php, HPDataType x);
void AdjustUp(HPDataType* a, int child);
void HeapPush(HP* php, HPDataType x)
{
assert(php);
if (php->size == php->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity * 2);
if (tmp == NULL)
{
perror("malloc fail");
return;
}
php->a = tmp;
php->capacity *= 2;
}
php->a[php->size] = x;
php->size++;
AdjustUp(php->a, php->size - 1);
}
void Swap(HPDataType* a, HPDataType* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustUp(HPDataType* a, int child)//插入数据后向上调整
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
删除堆中的数据使用的方法是将根节点的数据与最后一个数据交换，将堆容量减一即可。再交换过数据后，需要对堆进行向下调整(因为将最后一个数据也就是最小的数据放在了根节点)
void HeapPop(HP* php);
void AdjustDown(HPDataType* a, int n, int parent);
void AdjustDown(HPDataType* a, int n, int parent)
{
int child = parent * 2 + 1;
while (child < n)
{
if (child + 1 < n && a[child + 1] > a[child])
{
++child;
}
if (a[child] > a[parent])
{
Swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void HeapPop(HP* php)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, php->size, 0);
}
还有判空 堆的大小等操作:
typedef int HPDataType;
HPDataType HeapTop(HP* php);
bool HeapEmpty(HP* php);
int HeapSize(HP* php);
HPDataType HeapTop(HP* php)
{
assert(php);
return php->a[0];
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
int HeapSize(HP* php)
{
assert(php);
return php->size;
}
二.堆排序的讲解
想要使用堆排序，我们首先需要有一个堆，但是如果像上面那样手搓出一个堆，未免太过麻烦。有没有什么方法能让我们像使用其他排序一样(qsort、冒泡等)能直接使用堆排序，对数据进行排序呢?答案是肯定的！
举个例子:我们现在有一个数组，数组中有数据待排。我们首先应该建个堆、再进行排序。其中有两种不同的方式可以建堆———向上调整建堆和向下调整建堆时间复杂度分别为O(N*lgN）、O(N)
void HeapSort(int* a, int n)
{
// 建堆 -- 向上调整建堆 -- O(N*logN)
for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
}
int main()
{
int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序
HeapSort(a, 10);
return 0;
}
我们通过调试窗口观察是否达到我们的预期:
建好堆后，就是对数据进行排序,这里有一个重要的结论--------如果想要排升序就要建大根堆、想要排降序则需要建小根堆
最后效果如下:
void HeapSort(int* a, int n)
{
// 建堆 -- 向上调整建堆 -- O(N*logN)
/*for (int i = 1; i < n; ++i)
{
AdjustUp(a, i);
}*/
// 建堆 -- 向下调整建堆 -- O(N)
for (int i = (n - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(a, n, i);
}
int end = n - 1;
while (end > 0)
{
Swap(&a[end], &a[0]);
AdjustDown(a, end, 0);//排升序
--end;
}
}
int main()
{
int a[10] = { 2, 1, 5, 7, 6, 8, 0, 9, 4, 3}; // 对数组排序
HeapSort(a, 10);
return 0;
}