二叉堆、堆排序
【摘要】
目录
一，二叉堆
二，堆的调整
三，堆的创建
四，堆排序
五，堆元素更新
六，堆的插入
一，二叉堆
二叉堆是用数组实现的完全二叉树，也就是说物理结构是数组，逻辑结构是完全二叉树。
二叉堆分2种，最大堆和最小堆。
最大堆指的是，任何一个结点都比它的两个子结点（或1个或0个）要大，最小堆同理。
本文以最大堆为例进行展...
目录
一，二叉堆
二叉堆是用数组实现的完全二叉树，也就是说物理结构是数组，逻辑结构是完全二叉树。
二叉堆分2种，最大堆和最小堆。
最大堆指的是，任何一个结点都比它的两个子结点（或1个或0个）要大，最小堆同理。
本文以最大堆为例进行展示。
二，堆的调整
堆的调整指的是，给出一个完全二叉树，除了根结点之外，左子树是二叉堆，右子树是二叉堆，现在要调整元素位置，让整个树成为二叉堆。
其实就是把堆顶元素不停的往下塞，塞到合适的位置就停止了。
实现代码：
-
template<typename T>
-
bool cmp(T a, T b)
-
{
-
return a < b; //最大堆
-
}
-
-
template<typename T>
-
void exchange(T* a, T* b)
-
{
-
T tmp = *a;
-
*a = *b;
-
*b = tmp;
-
}
-
-
int LeftChild(int id)
-
{
-
return id * 2;
-
}
-
int RightChild(int id)
-
{
-
return id * 2 + 1;
-
}
-
int Parent(int id)
-
{
-
return id/2;
-
}
-
-
template<typename T>
-
void AdjustHeap(T* arr, int rootId, int size)
-
{
-
int largest = rootId, left = LeftChild(rootId), right = RightChild(rootId);
-
if (left < size && cmp(arr[largest], arr[left]))largest = left;
-
if (right < size && cmp(arr[largest], arr[right]))largest = right;
-
if (largest == rootId)return;
-
exchange(arr + rootId, arr + largest);
-
AdjustHeap(arr, largest, size);
-
}
时间复杂度：O（h），其中h是二叉堆的高度，h=Θ（log n），其中n=size，表示所有结点数目
三，堆的创建
给出一个数组，现在要交换元素位置，使得它变成一颗二叉堆。
实现代码：
-
template<typename T>
-
void InitHeap(T* arr, int size)
-
{
-
for (int i = size / 2; i >= 0; i--)AdjustHeap(arr, i, size);
-
}
原理：因为是完全二叉树，所以最后一层的结点数目小于总数的一半，也就是说，从size/2到0覆盖了除掉最后一层之外的所有结点。
时间复杂度：Θ（n），其中n=size，表示所有结点数目
四，堆排序
算法思路：
先构建二叉堆，于是数组第一个元素就是最大元素，把它和最后一个元素交换，
对于剩下的n-1个元素，直接调用AdjustHeap即可再次变成堆，于是得到了这n-1个元素里面的最大值，
依次类推，最后就变成增序的数组了。
-
template<typename T>
-
void HeapSort(T* arr, int size)
-
{
-
InitHeap(arr, size);
-
for (int i = size - 1; i > 0; i--) {
-
exchange(arr + i, arr);
-
AdjustHeap(arr, 0, i);
-
}
-
}
时间复杂度：O（n log n）
五，堆元素更新
-
template<typename T>
-
void HeapIncrese(T* arr, int size, int id, T newValue)
-
{
-
arr[id] = newValue;
-
while (id > 0 && cmp(arr[Parent(id)], arr[id])) {
-
exchange(arr + id, arr + Parent(id));
-
id = Parent(id);
-
}
-
}
-
template<typename T>
-
void HeapDecrese(T* arr, int size, int id, T newValue)
-
{
-
arr[id] = newValue;
-
AdjustHeap(arr, id, size);
-
}
-
template<typename T>
-
void HeapChange(T* arr, int size, int id, T newValue)
-
{
-
if (cmp(arr[id], newValue))HeapIncrese(arr, size, id, newValue);
-
else HeapDecrese(arr, size, id, newValue);
-
}
六，堆的插入
-
template<typename T>
-
void HeapInsert(T* arr, int &size,T value)
-
{
-
HeapIncrese(arr,size+1,size,value);
-
size++;
-
}
文章来源: blog.csdn.net，作者：csuzhucong，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/nameofcsdn/article/details/113484808
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）