heap.h
#pragma once
typedef int HPDataType;
typedef struct Heap
{
HPDataType* _array;
int _capacity;
int _size;
}Heap;
// 用数组初始化堆
void InitHeap(Heap* hp, HPDataType* array, int size);
// 初始化一个空堆
void InitEmptyHeap(Heap* hp, int capacity);
// 在堆中插入值为data的元素
void InsertHeap(Heap* hp, HPDataType data);
// 删除堆顶元素
void EraseHeap(Heap* hp);
// 获取堆中有效元素个数
int HeapSize(Heap* hp);
// 检测堆是否为空堆
int HeapEmpty(Heap* hp);
// 获取堆顶元素
HPDataType HeapTop(Heap* hp);
// 销毁堆
void DestroyHeap(Heap* hp);
//检测容量
void CheckCapacity(Heap* hp);
heap.c
#include "heap.h"
#include<stdio.h>
#include <assert.h>
#include <malloc.h>
void swap(HPDataType*a, HPDataType*b)
{
HPDataType tmp = 0;
tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustDown(HPDataType* array, int size, int parent)
{
int child = parent * 2 + 1;
//找双亲中较小的孩子
while (child < size)
{
//必须保证右孩子存在
if (child + 1 < size && array[child + 1] < array[child])
{
child += 1;
}
if (array[child] < array[parent])
{
swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
void AdjustUp(HPDataType* array, int size, int child)
{
int parent = (child - 1) / 2;
while (child != 0)
{
if (array[child] < array[parent])
{
swap(&array[child], &array[parent]);
child = parent;
parent = (child - 1) / 2;
}
}
}
void InitHeap(Heap* hp, HPDataType* array, int size)
{
assert(hp);
//把给的数组中的元素都拷贝到堆里,size是数组长度
hp->_array = (HPDataType*)malloc(sizeof(HPDataType)*size);
hp->_capacity = size;
hp->_size = 0;
for (int i = 0; i < size; ++i)
{
hp->_array[i] = array[i];
}
hp->_size = size;
int lastleaf = ((size - 2) >> 1);
//等于0也是要调整的
while (lastleaf >= 0)
{
AdjustDown(hp->_array, size, lastleaf);
lastleaf--;
}
}
void InitEmptyHeap(Heap* hp, int capacity);
void InsertHeap(Heap* hp, HPDataType data)
{
assert(hp);
CheckCapacity(hp);
hp->_array[hp->_size] = data;
hp->_size++;
AdjustUp(hp->_array, hp->_size, hp->_size - 1);
}
void EraseHeap(Heap* hp)
{
assert(hp);
if (hp->_size == 0)
{
return;
}
//把堆顶元素和最后一个元素互换,然后size--;在向下调整
swap(&hp->_array[0], &hp->_array[hp->_size - 1]);
hp->_size--;
AdjustDown(hp->_array, hp->_size, 0);
}
int HeapSize(Heap* hp)
{
assert(hp);
return hp->_size;
}
void CheckCapacity(Heap* hp)
{
assert(hp);
if (hp->_size == hp->_capacity)
{
int newcapacity = hp->_capacity * 2;
HPDataType* tmp = (HPDataType*)malloc(sizeof(HPDataType)*newcapacity);
if (tmp == NULL)
{
return;
}
for (int i = 0; i < hp->_size; ++i)
{
tmp[i] = hp->_array[i];
}
//释放旧空间
free(hp->_array);
hp->_array = tmp;
hp->_capacity = newcapacity;
}
}
int HeapEmpty(Heap* hp)
{
assert(hp);
if (hp->_size == 0)
{
return -1;
}
return 1;
}
HPDataType HeapTop(Heap* hp)
{
assert(hp);
if (hp->_size == 0)
{
return -1;
}
return hp->_array[0];
}
void DestroyHeap(Heap* hp)
{
assert(hp);
if (hp->_array != NULL)
{
free(hp->_array);
hp->_array = NULL;
hp->_size = 0;
hp->_capacity = 0;
}
}
void HeapTest()
{
Heap hp;
int a[] = { 27, 15, 19, 18, 28, 34, 65, 49, 25, 37 };
InitHeap(&hp, a, sizeof(a) / sizeof(a[0]));
printf("size=%d\n", HeapSize(&hp));
printf("堆顶:%d\n", HeapTop(&hp));
EraseHeap(&hp);
printf("删除堆顶元素成功!\n");
printf("size=%d\n", HeapSize(&hp));
printf("堆顶:%d\n", HeapTop(&hp));
InsertHeap(&hp, 13);
printf("插入元素成功!\n");
printf("size=%d\n", HeapSize(&hp));
printf("堆顶:%d\n", HeapTop(&hp));
InsertHeap(&hp, 0);
printf("插入元素成功!\n");
printf("size=%d\n", HeapSize(&hp));
printf("堆顶:%d\n", HeapTop(&hp));
EraseHeap(&hp);
printf("删除堆顶元素成功!\n");
printf("size=%d\n", HeapSize(&hp));
printf("堆顶:%d\n", HeapTop(&hp));
//DestroyHeap(&hp);
}
int main()
{
HeapTest();
system("pause");
return 0;
}
代码运行测试图:
对代码进行优化:完成可以指定创建大堆还是小堆
创建一个函数指针:
typedef int(*PCom)(HPDataType, HPDataType);
typedef struct Heap
{
HPDataType* _array;
int _capacity;
int _size;
PCom compare;
}Heap;
给初始化和向上向下调整加入参数:
void InitHeap(Heap* hp, HPDataType* array, int size,PCom compare);
void AdjustDown(HPDataType* a, int size, int parent, PCom compare)
void AdjustUp(HPDataType* a, int size, int child,PCom compare)
具体比较的实现:
int less(HPDataType a, HPDataType b)
{
return a<b;
}
int Greater(HPDataType a, HPDataType b)
{
return a>b;
}
对原先比较的修改:
向下调整中:
if (child + 1 < size && compare(a[child + 1] , a[child]))
{
child += 1;
}
if (compare(a[child] , a[parent]))
{
swap(&a[child], &a[parent]);
parent = child;
child = parent * 2 + 1;
}
向上调整中:
if (compare(a[child] , a[parent]))
{
swap(&a[child], &a[parent]);
child = parent;
parent = (child - 1) / 2;
}
调用时的参数传递:
AdjustDown(hp->_array, size, lastleaf,hp->compare);
AdjustUp(hp->_array, hp->_size, hp->_size - 1,hp->compare);
代码运行测试图:
堆的排序:
void HeapAdjust(int* array, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
// 找左右孩子中较大的孩子
if (child + 1 < size && array[child + 1] > array[child])
child += 1;
if (array[child] > array[parent])
{
Swap(&array[child], &array[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
return;
}
}
}
void HeapSort(int* array, int size)
{
//建堆
int root = ((size - 1) >> 1);
for (root; root >= 0; --root)
{
HeapAdjust(array, size, root);
}
//排序
int end = size - 1;
while (end != 0)
{
swap(&array[0], &array[end]);
HeapAdjust(array, end, 0);
end--;
}
}
TOP K问题在【数据结构---26】中
