目录
一、二叉树的顺序结构
二、堆的概念及结构
三、堆的实现
四、堆的应用
4.1 堆排序
4.1.1 建堆
4.1.2 利用堆删除思想来进行排序
4.2 TOP-K问题
很多时候,我们竞争对手是我们自己,而不是别人。
一、二叉树的顺序结构
二、堆的概念及结构
理解:堆分为大堆和小堆;大堆/大根堆:树中父亲的数据都大于等于孩子;小堆/小根堆:树中父亲的数据都小于等于孩子
堆解决的问题:堆排序、TOP-K
三、堆的实现
heap.h
#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
size_t size;
size_t capacity;
}HP;
void HeapInit(HP* php);
void HeapDestory(HP* php);
void HeapPrint(HP* php);
void Swap(HPDataType* pa, HPDataType* pb);
void HeapPush(HP* php, HPDataType x);
void HeapPop(HP* php);
bool HeapEmpty(HP* php);
size_t HeapSize(HP* php);
HPDataType HeapTop(HP* php);
heap.c
#include "heap.h"
void HeapInit(HP* php)
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestory(HP* php)
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
//按数组打印
void HeapPrint(HP* php)
{
assert(php);
for (size_t i = 0; i < php->size; ++i)
{
printf("%d ", php->a[i]);
}
printf("\n");
}
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
bool HeapEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
//多少个数据
size_t HeapSize(HP* php)
{
assert(php);
return php->size;
}
HPDataType HeapTop(HP* php)
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
void AdjustUp(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
//这个比较取决于大小堆
//小堆
//最后一次比较,是parent是0,进行比较,当再次进行调整后。就不需要进行了,此时的child等于0,parent也是0[因为size_t是正整数】
//-1/2还是等于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;//跳出循环
}
}
}
void HeapPush(HP* php, HPDataType x)
{
assert(php);
数据插入数组后
//先判断是否有地方进行扩容
if (php->size == php->capacity)
{
size_t newCapacity = php->capacity == 0 ? 4 : (2 * (php->capacity));
//开辟空间,要有一个临时变量进行开辟,否则如果开辟失败,里面的数据就都找不到了
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
php->a = tmp;
php->capacity = newCapacity;
}
php->a[php->size] = x;
(php->size)++;//先插入,后size++,此时size这个下标的位置并没有值
向上调整的算法,成为堆
size_t child = (php->size) - 1;
AdjustUp(php->a, child);
}
堆的插入:先插入一个数字到数组的尾上【插入的这个数字后,可能不满足堆的概念】,再进行向上调整算法,直到满足堆
void AdjustDown(HPDataType* a, size_t root, size_t size)
{
//找出小的
//注意:可能没有右孩子
size_t parent = root;
size_t child = parent * 2 + 1;
while (child < size)
{
//避免越界
if (child + 1 < size && a[child] > a[child + 1])
{
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);
//当删除数据的时候,要判断有没有值
assert(php->size > 0);
Swap(&php->a[0], &php->a[php->size - 1]);
php->size--;
AdjustDown(php->a, 0, php->size);
}
堆的删除:删除堆是删除堆顶【最小或者最大的数据】的数据,将堆顶的数据和最后一个数据交换,然后删除数组最后一个数据,再进行向下调整算法。【先交,后删除,在进行向下调整算法】
向下调整算法:首先找出两个孩子节点中小(大)的那一个,然后去和父节点比较,进行交换,父节点的数据总是小于等于(大于等于)子节点,然后再从交换的孩子向下比较】
堆的插入、删除的时间复杂度为O(logN)
四、堆的应用
4.1 堆排序
堆排序即利用 堆的思想来进行排序,总共分为两个步骤:1. 建堆(在数组上建堆,那么堆排序的空间复杂度为O(1))升序:建大堆降序:建小堆2. 利用堆删除思想来进行排序
4.1.1 建堆
建堆有两种方法:(1)使用向上调整,插入数据的思想建堆。插入数据到新的数组,就是在不断插入的过程中向上调整实现排序 【代码1】(2)使用向下调整【从倒数第一个非叶子节点开始,即最后一个节点的父亲,即(size-1-1)/2】【找到这个父亲的节点,向下排序,然后这个父亲节点依次减一【就找到各个小堆】,依次向下排序,就成为了一个堆。】【代码2】
【建堆结束后,可以让数组成为一个堆】
代码1展示:
void Swap(HPDataType* pa, HPDataType* pb)
{
HPDataType tmp = *pa;
*pa = *pb;
*pb = tmp;
}
void AdjustUp(HPDataType* a, size_t child)
{
size_t parent = (child - 1) / 2;
//这个比较取决于大小堆
//小堆
//最后一次比较,是parent是0,进行比较,当再次进行调整后。就不需要进行了,此时的child等于0,parent也是0[因为size_t是正整数】
//-1/2还是等于0
while (child > 0)
{
if (a[child] < a[parent])
{
Swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;//跳出循环
}
}
}
void HeapSort(int* a, int n)
{
//升序,建大堆,向上
size_t i = 0;
for (i = 1; i < n; ++i)
{
AdjustUp(a, i);
}
}
int main()
{
int a[] = { 4, 3, 10 , 2, 5, 9 };
HeapSort(a, sizeof(a) / sizeof(int));
for (int i = 0; i < sizeof(a) / sizeof(int); i++)
{
printf("%d ", a[i]);
}
printf("\n");
return 0;
}
代码2展示:
void HeapSort(int* a, int n)
{
//升序,建堆,向上
/*int i = 0;
for (i = 1; i < n; ++i)
{
AdjustUp(a, i);
}*/
//向下
int i = 0;
for (i = (n - 2) / 2; i >= 0; --i)
{
AdjustDown(a, i, n);
}
}
建堆的时间复杂度:
向上建堆:首先每一层的节点数为2^(h-1);建堆是从第二层开始插入数据,第二层有2^(2-1)个节点,成为一个堆,向上调整的最坏次数为2^(2-1)*1;第三层有2^(3-1)个节点,成为一个堆,向上调整的次数为2^(3-1)*2;……;那么向上调整累积建堆次数为2^(2-1)*1+2^(3-1)*2+2^(4-1)*3+……+2^(h-1)*(h-1)。这是一个等差数列*等比数列。利用错位相减,可以算出次数为2^h*(h-2)+2; 最终时间复杂度为O(N*logN)
向下建堆:首先每一层的节点数为2^(h-1);建堆是从(从倒数第一个非叶子节点开始)【这个非叶子节点不一定是倒数第二层的最后一个,但是此时可以把堆看做满级二叉树【两者的时间复杂度,差别不大】,那么此时的非叶子节点就是倒数第二层的最后一个】倒数第二层开始向下调整,一直到第一层向下调整结束,每一层有2^(h-1)个节点,每一个节点和下面部分成为一个堆,每个节点向下调整的最坏次数为2^(h-1)*(h);那么向下调整累积建堆次数为2^0*(h-1)+2^1*(h-2)+2^2*(h-2)+……+2^(h-2)*1,这是一个等差数列*等比数列。利用错位相减,可以算出次数为2^h-1-h,因为2^h-1=N,; 最终时间复杂度为O(N).。
总结:建堆最好用向下建堆
建堆:升序建大堆,降序建小堆。【如果升序建小堆,最小的数已经在第一个位置了,再次选出次小的,需要不断建堆选数。那么总的时间复杂度为O(N^2),既然这样,还不如直接遍历选数,时间复杂度也是O(N^2)】【升序应该建大堆】
4.1.2 利用堆删除思想来进行排序
升序,大堆为例:建立大堆之后,最大值就在最前面,然后,最大值和最后一个值【下标为n-1】进行互换,然后不管n-1这个下标进行建堆,然后最大值再次与最后一个值进行【下标为n-2】进行互换。一直到下标为0的元素与下标为1的元素进行过交换,数组就完成了排序。【时间复杂度为:O(N*logN)】
void HeapSort(int* a, int n)
{
//升序,建堆,向上
/*int i = 0;
for (i = 1; i < n; ++i)
{
AdjustUp(a, i);
}*/
//向下
int i = 0;
for (i = (n - 2) / 2; i >= 0; --i)
{
AdjustDown(a, i, n);
}
size_t end = n - 1;
while (end > 0)
{
Swap(&a[0], &a[end]);
AdjustDown(a, 0, end);
--end;
}
}
4.2 TOP-K问题
N个数找出最大/最小的前K个文章来源:https://www.toymoban.com/news/detail-548812.html
时间复杂度为:O(K+logK*(N-K));空间复杂度为:O(K).文章来源地址https://www.toymoban.com/news/detail-548812.html
void PrintTopK(int* a, int n, int k)
{
// 建堆--用a中前k个元素建堆
int* kminHeap = (int*)malloc(sizeof(int) * k);
if (kminHeap == NULL)
{
printf("malloc fail \n");
exit(-1);
}
//前k个元素,放在数组里面
for (int i = 0; i < k; ++i)
{
kminHeap[i] = a[i];
}
// 建小堆
for (int j = (k - 2) / 2; j >= 0; --j)
{
AdjustDown(kminHeap, j, k);//k指的是下标,数组最后元素的下标,为了方便找到父节点
}
// 2. 将剩余n-k个元素依次与堆顶元素交换,不满则则替换
for (int i = k; i < n; ++i)
{
if (a[i] > kminHeap[0])
{
kminHeap[0] = a[i];
AdjustDown(kminHeap, 0, k);
}
}
for (int j = 0; j < k; ++j)
{
printf("%d ", kminHeap[j]);
}
printf("\n");
free(kminHeap);
}
void TestTopk()
{
int n = 10000;
int* a = (int*)malloc(sizeof(int) * n);
srand(time(0));
for (size_t i = 0; i < n; ++i)
{
a[i] = rand() % 1000000;
}
a[5] = 1000000 + 1;
a[1231] = 1000000 + 2;
a[531] = 1000000 + 3;
a[5121] = 1000000 + 4;
a[115] = 1000000 + 5;
a[2305] = 1000000 + 6;
a[99] = 1000000 + 7;
a[76] = 1000000 + 8;
a[423] = 1000000 + 9;
a[0] = 1000000 + 1000;
PrintTopK(a, n, 10);
}
到了这里,关于【数据结构】二叉树——堆如何实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!