数据结构-堆-详解
- 1.性质
- 大根堆
- 小根堆
- 2.实现
- 2.1struct Heap、HeapInit、HeapDestroy
- 2.2HeapPush
- AdjustUp
- 2.3HeapPop
- AdjustDown
- 2.4HeapTop、HeapSize、HeapEmpty
- 3.应用
- 3.1堆排
- 建堆
- 排序
- 3.2TopK问题
1.性质
堆是一种特殊的完全二叉树,其父节点总是不大于/不小于 子节点。
相比于普通二叉树,堆更适合用顺序结构的数组存储。
大根堆
其中任一父节点都不小于子节点。
逻辑结构:
储存结构:
小根堆
其中任一父节点都不大于子节点。
逻辑结构:
储存结构:
2.实现
2.1struct Heap、HeapInit、HeapDestroy
堆的结构体、堆的初始化、堆的销毁。
从上面的大小根堆可以看出,堆在实现上是一个顺序表,而逻辑上是二叉树。
因此,这几步与顺序表几乎完全一致:
typedef int HeapDataType;
typedef struct Heap
{HeapDataType* a;int size;int capacity;
}Heap;void HeapInit(Heap* php)
{assert(php);php->a = (HeapDataType*)malloc(sizeof(HeapDataType) * 4);if (!php->a){perror("HeapInit::malloc");return;}php->size = 0;php->capacity = 4;
}void HeapDestroy(Heap* php)
{assert(php);free(php->a);php->a = NULL;php->capacity = php->size = 0;
}
2.2HeapPush
插入元素。
void HeapPush(Heap* php, HeapDataType x)
{assert(php);if (php->size == php->capacity){HeapDataType* tmp = (HeapDataType*)realloc(php->a,sizeof(HeapDataType) * php->capacity * 2);if (!tmp){perror("HeapDataType::realloc");return;}php->a = tmp;php->capacity *= 2;}php->a[php->size] = x;php->size++;AdjustUp(php->a,php->size-1);
}
先判断是否需要扩容,再插入。
但这是个堆,因此需要对数据进行调整。
此处以大根堆为例,使用向上调整法AdjustUp
。
AdjustUp
大根堆需要满足其中任一父节点都不小于子节点。
当插入一个节点后,可以将其与父节点比较,不满足条件则交换,最多调到根。
void AdjustUp(HeapDataType* a, int child)
{assert(a);int parent = (child - 1) / 2;while (parent >= 0){if (a[child] > a[parent])Swap(a + child, a + parent);elsebreak;child = parent;parent = (child - 1) / 2;}
}//有小bug
由公式得:父节点下标parent = (child - 1) / 2
。
进入循环:
- 如果不满足条件,则交换
Swap
。
void Swap(HeapDataType* a,HeapDataType* b)
{assert(a && b);HeapDataType tmp = *a;*a = *b;*b = tmp;
}
这里又封装了一个函数,因为这部分需要用到交换的地方还挺多的。
- 如果满足条件,由于堆的性质,可直接
break
结束循环。
一个小bug:需注意的是循环结束条件parent >= 0
,当运行时,会发现程序能跑,没出问题。
但可以分析一下:如果child
已经为根,即child == 0
,算一下parent
:(0 - 1)/2 = 0
。
下图的情景出现了!
当然,这里的bug是能改的,用child
作为判断条件即可:
//while (parent >= 0)
while(child>0)
2.3HeapPop
删除堆顶元素。
堆顶元素为堆的最大/小值,因此,删除堆顶元素才具有一定意义。
挪动删除,
是不行的:
两个原因:
- 效率低下
- 父子关系被打乱
正确方法:
void HeapPop(Heap* php)
{assert(php);assert(!HeapEmpty(php));Swap(php->a, php->a + php->size - 1);php->size--;AdjustDown(php->a, php->size, 0);
}
这里,先将最前的与最后的交换(Swap
),
然后删除最后一个元素(size--
),
最后,向下调整(AdjustDown
)。
AdjustDown
void AdjustDown(HeapDataType* a, int n, int parent)
{assert(a);int child = parent * 2 + 1;while (child < n){if ((child + 1) < n && a[child] < a[child + 1])child++;if (a[parent] < a[child])Swap(a + parent, a + child);elsebreak;parent = child;child = parent * 2 + 1;}
}
这里传了三个参数,其中parent
为需要调整的父节点的位置,此处传0
。
while
循环,会在child
下标小于堆大小n
的情况下继续执行,这表示还有子节点存在。
由于是大根堆,向下调整时,先选出子节点中的较大值,再与父节点比较,满足则break
出循环,不满足条件则交换,继续循环。
2.4HeapTop、HeapSize、HeapEmpty
取堆顶元素、堆的大小、判空。
HeapDataType HeapTop(Heap* php)
{assert(php);return php->a[0];
}int HeapSize(Heap* php)
{assert(php);return php->size;
}bool HeapEmpty(Heap* php)
{assert(php);return php->size == 0;
}
3.应用
3.1堆排
即使用堆进行排序。
给一个数组,要使用堆排,前提是必须有个堆,因此第一步为建堆。
那么,建大堆还是小堆?怎么建堆?
建什么堆,这里有个规律:
- 升序建大堆
- 降序建小堆
如何建堆,有两种方法:
- 使用向上调整法,插入建堆
- 使用向下调整法,调整建堆
建堆
向上调整法:
void HeapSort(int* a, int n)
{//建堆for (int i = 0; i < n; i++){AdjustUp(a, i);}//排序
}
向下调整法:
使用向下调整法建堆,需满足左、右子树必须是堆。
随便给的数组肯定不能满足此条件,因此不能从根节点开始建堆,需要找倒数第一个非叶子节点:
叶节点是堆,空节点也是堆,因此,从第一个非叶子节点开始使用向下调整法,不断调整直到根节点。
void HeapSort(int* a, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//排序
}
在实际使用中,通常使用向下调整法建堆,因为向上调整法的时间复杂度为O(N*logN)
,而向下调整法的时间复杂度为O(N)
。
排序
这里使用的是堆删除的思想来排序。
现在假设排升序,并且已经建好了一个大堆:
Pop
一下,最大的就跑最后去了,然后重复此过程,就能排成升序。
这也验证了:
- 升序建大堆
- 降序建小堆
完整代码:
void HeapSort(int* a, int n)
{//建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(a, n, i);}//排序int size = n;while (size--){Swap(a, a + size);AdjustDown(a, size, 0);}
}
3.2TopK问题
即在很多数中找出最… 的K
个 数。
这里的很多一般是真的很多,因此不能在对全部数据进行排序,因为浪费空间。
解决方法是用这些数的前K
个建个堆,在将其余满足条件的数插入堆中。
建堆:
- 求最大,建小堆
- 求最小,建大堆
插入:
依次将其余的数与堆顶的数进行比较,根据需要进行替换,最后堆中的K
个数即为所求。
希望本篇文章对你有所帮助!并激发你进一步探索数据结构的兴趣!
本人仅是个C语言初学者,如果你有任何疑问或建议,欢迎随时留言讨论!让我们一起学习,共同进步!
相关文章:
数据结构-二叉树-基础知识