数据结构堆的实现以及堆的面试题
程序员文章站
2024-02-11 19:40:16
...
堆
堆的特点
堆有大堆和小堆之分
小堆:
①任意结点的关键码均小于等于他的左右孩子的关键码
②位于堆顶的结点的关键码最小
③从根结点到每个结点的路径上数组元素组成的序列都是递增的
大堆:
①任意结点的关键码均大于等于他的左右孩子的关键码
②位于堆顶的结点的关键码最大
③从根结点到每个结点的路径上数组元素组成的序列都是递减的
堆存储在下标为0的数组中,因此在堆中给定下标为i的结点时有:
①如果i=0,结点i是根节点,没有双亲节点;否则结点i的双亲结点为
结点(i-1)/2
②如果2 * i + 1 <= n - 1(n为堆中结点个数),则结点i的左孩子为结
点2 * i + 1,否则结点i无左孩子
③如果2 * i + 2 <= n - 1(同上),则结点i的右孩子为结点2 * i + 2,
否则结点i无右孩子
堆的实现
heap.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int HPDataType;
typedef int (*PCompare)(HPDataType left, HPDataType right);//函数指针,用小堆就选Less,用大堆就选Greater
typedef struct Heap
{
HPDataType *_hp;
int _size;//堆中的元素个数
int _capacity;//堆的容量
PCompare _com;
}Heap;
// 小于比较
int Less(HPDataType left, HPDataType right);
// 大于比较
int Greater(HPDataType left, HPDataType right);
// 初始化堆
void InitHeap(Heap* hp);
// 创建堆
void CreateHeap(Heap* hp, int* array, int size, PCompare com);
//检查扩容
void _CheckCapacity(Heap* hp);
// 在堆中插入元素data
void InsertHeap(Heap* hp, HPDataType data);
// 删除堆顶的元素
void RemoveHeap(Heap* hp);
// 获取堆中有效元素个数
int SizeHeap(Heap* hp);
// 检测堆是否为空
int EmptyHeap(Heap* hp);
// 获取堆顶元素
HPDataType TopHeap(Heap* hp);
// 销毁堆
void DestroyHeap(Heap* hp);
// 向下调整
void AdjustDown(Heap* hp, int parent);
// 向上调整
void AdjustUp(Heap* hp, int child);
heap.c
#include "heap.h"
int Less(HPDataType left, HPDataType right)
{
return left < right;
}
int Greater(HPDataType left, HPDataType right)
{
return left > right;
}
void InitHeap(Heap* hp)
{
assert(hp);
hp->_hp = (HPDataType*)malloc(3 * sizeof(HPDataType));//初始化开辟多少都行
hp->_capacity = 3;
hp->_size = 0;
}
void Swap(HPDataType *left, HPDataType*right)
{
HPDataType tmp = 0;
tmp = *left;
*left = *right;
*right = tmp;
}
void AdjustUp(Heap* hp, int child)
{
assert(hp);
int parent = (child - 1) / 2;//找出父母结点下标
while (child)//只要child还为非零,就继续循环
{
if (hp->_com(hp->_hp[child], hp->_hp[parent]))//是否需要父母结点
//与孩子结点交换关键码
{
Swap(&hp->_hp[child], &hp->_hp[parent]);
child = parent;//此时孩子结点上移到父母结点
parent = (child - 1) / 2;//计算新的父母结点
}
else
return;
}
}
void AdjustDown(Heap* hp, int parent)
{
assert(hp);
if (NULL == hp)
return;
int child = parent * 2 + 1;//计算左孩子结点下标
while (child < hp->_size)//只要孩子结点下标不越界
{
if (child + 1 < hp->_size&&hp->_com(hp->_hp[child+1],hp->_hp[child]))
//是否需要左右孩子交换关键码,我是以左孩子是否与父母交换关键码为前提
{
Swap(&hp->_hp[child], &hp->_hp[child + 1]);
}
if (hp->_com(hp->_hp[child], hp->_hp[parent]))//是否左孩子与父母交换关键码
{
Swap(&hp->_hp[child], &hp->_hp[parent]);
parent = child;//父母结点移到孩子结点,当做下一个父母结点
child = parent * 2 + 1;
}
else
return;
}
}
void CreateHeap(Heap* hp, int* array, int size, PCompare com)
{
assert(hp);
int root = (size - 2) / 2;//找到最后一个非叶子结点的结点
int i = 0;
hp->_hp = (HPDataType*)malloc(size * sizeof(HPDataType));
if (hp == NULL)
return;
for (i = 0; i < size; i++)
{
hp->_hp[i] = array[i];
}
hp->_capacity = size;
hp->_size = size;
hp->_com = com;
while (root>=0)//从当前结点一直向下调整到下标为零的结点
{
AdjustDown(hp,root);
root--;
}
}
void _CheckCapacity(Heap* hp)
{
assert(hp);
int i = 0;
HPDataType *new = NULL;
int newcapacity = hp->_capacity * 2;
new = (HPDataType*)malloc(newcapacity * sizeof(HPDataType));
if (new == NULL)
return;
for (i = 0; i < hp->_size; i++)
{
new[i] = hp->_hp[i];
}
free(hp->_hp);
hp->_hp = new;
hp->_capacity = newcapacity;
}
void InsertHeap(Heap* hp, HPDataType data)
{
assert(hp);
if (hp->_capacity == hp->_size)
_CheckCapacity(hp);
hp->_hp[hp->_size] = data;//一定要先插入后size++
AdjustUp(hp, hp->_size);
hp->_size++;
}
void RemoveHeap(Heap* hp)
{
assert(hp);
if (NULL == hp)
return;
hp->_hp[0] = hp->_hp[hp->_size - 1];
hp->_size--;//一定要先size--,后向下调整,否则他会把删除的结点也调整了
AdjustDown(hp, 0);
}
int SizeHeap(Heap* hp)
{
assert(hp);
return hp->_size;
}
int EmptyHeap(Heap* hp)
{
assert(hp);
return 0 == hp->_size;
}
HPDataType TopHeap(Heap* hp)
{
assert(hp);
return hp->_hp[0];
}
void DestroyHeap(Heap* hp)
{
assert(hp);
if (hp)
{
free(hp);
hp->_capacity = 0;
hp->_size = 0;
}
}
优先级队列
heap.h
typedef struct PriorityQueue
{
Heap hp;
}PriorityQueue;
//初始化
void InitPriorityQueue(PriorityQueue* q);
//入队列
void PushPriorityQueue(PriorityQueue* q, HPDataType data);
//出队列
void PopPriorityQueue(PriorityQueue* q);
//取队头元素
void TopPriorityQueue(PriorityQueue* q);
//队列长度
int SizePriorityQueue(PriorityQueue* q);
//判空
int EmptyPriorityQueue(PriorityQueue* q);
heap.c
void InitPriorityQueue(PriorityQueue* q)
{
InitHeap(&q->hp);
}
void PushPriorityQueue(PriorityQueue* q, HPDataType data)
{
InsertHeap(&q->hp, data);
}
void PopPriorityQueue(PriorityQueue* q)
{
RemoveHeap(&q->hp);
}
void TopPriorityQueue(PriorityQueue* q)
{
return TopHeap(&q->hp);
}
int SizePriorityQueue(PriorityQueue* q)
{
return SizeHeap(&q->hp);
}
int EmptyPriorityQueue(PriorityQueue* q)
{
return EmptyHeap(&q->hp);
}
堆排序(降序,用小堆)
堆排序的原理:
①将堆顶元素和堆中最后一个元素交换
②此时数组最后一个元素已经排好序了,因此将堆中元素减少一个
③此时堆结构可能被破坏,再向下调整使其满足堆的性质
④将以上三个步骤循环起来,直到排序完数组中的所有元素
void _AdjustDown(int *array, int size, int parent)
{
int child = parent * 2 + 1;
while (child < size)
{
if (child + 1 < size&&array[child + 1] < array[child])
{
Swap(&array[child + 1], &array[child]);
}
if (array[parent] > array[child])
{
Swap(&array[parent], &array[child]);
parent = child;
child = parent * 2 + 1;
}
else
return;
}
}
void MakeHeap(int *array, int size)
{
int root = (size - 2) / 2;
while (root >= 0)
{
_AdjustDown(array,size, root);
root--;
}
}
void HeapSort(int *array, int size)
{
MakeHeap(array, size);//把传过来的数组创建成堆
while (size)//调整完所有元素
{
Swap(&array[0], &array[size - 1]);//交换堆顶元素和堆中最后一个元素
size--;//减少堆中元素一个
_AdjustDown(array, size, 0);//向下调整
}
}
测试
test.c
#include "heap.h"
int main()
{
//Heap hp;//被注释了的是测试堆的实现的代码,没被注释的是测试堆排序的代码,优先级队列大家就自己测试吧
int i = 0;
int array[] = { 53,17,78,9,45,65,87,23,31 };
//InitHeap(&hp);
//CreateHeap(&hp, array, sizeof(array)/sizeof(array[0]), Less);
//for (i = 0; i < hp._size; i++)
//{
// printf("%d ", hp._hp[i]);
//}
//printf("\n");
//printf("%d ", TopHeap(&hp));
//printf("%d ", SizeHeap(&hp));
//printf("\n");
int size = sizeof(array) / sizeof(array[0]);
HeapSort(array,size);
for (i = 0; i < size; i++)
{
printf("%d ", array[i]);
}
printf("\n");
//InsertHeap(&hp,11);
//for (i = 0; i < hp._size; i++)
//{
// printf("%d ", hp._hp[i]);
//}
//printf("\n");
//printf("%d ", TopHeap(&hp));
//printf("%d ", SizeHeap(&hp));
//printf("\n");
//RemoveHeap(&hp);
//for (i = 0; i < hp._size; i++)
//{
// printf("%d ", hp._hp[i]);
//}
//printf("\n");
//printf("%d ", TopHeap(&hp));
//printf("%d ", SizeHeap(&hp));
system("pause");
return 0;
}
推荐阅读