当前位置 博文首页 > L_add的博客：堆（堆排序）---完全二叉树
（一)堆
1、定义：堆（heap）是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。
假设父亲的下标是parent
leftchild = parent * 2+1
rightchild = parent * 2+2
2、性质
a.堆中某个结点的值总是不大于或不小于其父结点的值；
b.堆总是一棵完全二叉树。
(二)分类
1、小根堆：父亲小于等于孩子
2、大根堆：父亲大于等于孩子
(三)实现堆排序（小堆）
void Swap(int* a,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void ADJustDown(int* 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[parent],&a[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
int main()
{
int a[] = {27,15,19,18,28,34,65,49,25,37};
int n = sizeof(a)/sizeof(a[0]);
ADJustDown(a,n,0);
return 0;
}
问题：左右子树不是小堆怎么办？
void Swap(int* a,int* b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
void ADJustDown(int* 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[parent],&a[child]);
parent = child;
child = parent * 2 + 1;
}
else
break;
}
}
int main()
{
int a[] = {15,18,28,34,65,19,49,25,37,27};//最大下标为n-1
int n = sizeof(a)/sizeof(a[0]);
//建堆
for(int i = (n-1-1) / 2;i >= 0;i--)
ADJustDown(a,n,0);
return 0;
}
#include<stdio.h>
void Swap(int* p1, int* p2)
{
int tmp = *p1;
*p1 = *p2;
*p2 = tmp;
}
void AdjustDown(int* 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[parent], &a[child]);
parent = child;
child = parent * 2 + 1;
}
else{
break;
}
}
}
// 排升序，建大堆，还是小堆呢？-》大堆
void HeapSort(int* a, int n)
{
// 建堆 -》 时间复杂度是多少？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[0], &a[end]);
// 选出次大的
AdjustDown(a, end, 0);
--end;
}
}
int main()
{
int a[] = { 15, 18, 28, 34, 65, 19, 49, 25, 37, 27 };
int n = sizeof(a) / sizeof(a[0]);
HeapSort(a, n);
return 0;
}
