堆排序
1.堆的概念及结构
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为
小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
2.堆的性质：
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
3.堆的实现
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;
int size;
int capacity;
}Heap;
（1）堆调整向下算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。
int a[] = {27,15,19,18,28,34,65,49,25,37};
交换函数：
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;
}
}
}
（*）向下调整算法时间复杂度
假设这个堆为满二叉树，堆高为h，假设每层高度为hi，假设每层结点数为ni，则建堆的时间复杂度为t(n)=Σni*hi,即：
（2）堆调整向上算法
void AdjustUp(int* a, int n, int child)
{
int parent = (child-1)/2;
while (child > 0)
{
if (a[child] > a[parent])
{
Swap(&a[parent], &a[child]);
child=parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
（3）堆的创建
下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。
int a[] = {1,5,3,8,7,6};
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
assert(hp);
hp->a = (HPDataType*)malloc(sizeof(HPDataType) * n);
if (hp->a == NULL)
{
printf("malloc fail\n");
exit(-1);
}
memcpy(hp->a, a, sizeof(HPDataType) * n);
hp->size = n;
hp->capacity = n;
for (int i = (hp->size - 1 - 1) / 2; i >= 0; --i)
{
AdjustDown(hp->a, hp->size, i);
}
}
（4）堆的销毁
void HeapDestory(Heap* hp)
{
assert(hp);
free(hp->a);
hp->size = hp->capacity = 0;
}
（5）堆的插入
先插入一个80到数组的尾上，再进行向上调整算法，直到满足堆。
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
if (hp->size == hp->capacity)
{
HPDataType* tmp = (HPDataType*)realloc(hp->a, hp->size * 2 * sizeof(HPDataType));
if (tmp == NULL)
{
printf("malloc fail\n");
exit(-1);
}
hp->a = tmp;
hp->capacity *= 2;
}
hp->a[hp->size - 1] = x;
hp->size++;
AdjustUp(hp->a, hp->size, hp->size-1);
}
（6）堆的删除
删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调整算法。
void HeapPop(Heap* hp)
{
assert(hp);
assert(hp->size>0);
Swap(&hp->a[0], &hp->a[hp->size-1]);
hp->size--;
AdjustDown(hp->a, hp->size, 0);
}
（6）取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
assert(hp->size > 0);
return hp->a[0];
}
（7）堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
（8）堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size==0;
}
（9）堆的打印
int HeapPrint(Heap* hp)//打印堆
{
for (int i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
}
printf("/n");
int num = 0;
int leveSize = 1;
for (int i = 0; i < hp->size; i++)
{
printf("%d ", hp->a[i]);
num++;
if (num == leveSize)
{
printf("\n");
leveSize *= 2;
num = 0;
}
}
}
（10）对数组进行堆排序
void HeapSort(int* a, int 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--;
}
}
4.堆的应用
（1）TopK问题
题目描述：
输入整数数组 arr ，找出其中最小的 k 个数
示例：
输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]
实现思路：
第一步：先取出数组中的前K个数据，建大堆
第二步：依次剩下N-K个数，和堆顶的数据比较。如果比堆顶的数据小，则替换堆顶的数据，然后调整堆（向下调整法）
第三步：最后堆里的就是最小的K个数
时间复杂度：O(N*logK)
空间复杂度：O(K)
实现代码：
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;
}
}
}
int* getLeastNumbers(int* arr, int arrSize, int k, int* returnSize)
{
if(k==0)
{
*returnSize=0;
return NULL;
}
int* arrRet=(int*)malloc(sizeof(int)*k);
for(int i=0;i<k;i++)
{
arrRet[i]=arr[i];
}
for(int j=(k-1-1)/2;j>=0;j--)
{
AdjustDown(arrRet,k,j);
}
for(int i=k;i<arrSize;i++)
{
if(arr[i]<arrRet[0])
{
arrRet[0]=arr[i];
AdjustDown(arrRet,k,0);
}
}
*returnSize=k;
return arrRet;
}
相关文章
精彩导读
热门资讯