数据结构堆的实现(C实现)
一、堆
当一颗完全二叉树用顺序表来存储时,其被称为堆。
- 堆总是一棵完全二叉树
- 堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值
其可以被用来解决top k 问题 或 堆排序
下面就是要实现的堆的功能 重点在于堆的插入 和 堆的删除
//堆的构建
void HeapInit(Heap* hp);
//堆的销毁
void HeapDestroy(Heap* hp);
//堆的插入
void HeapPush(Heap* hp, HPDataType x);
//堆的删除
void HeapPop(Heap* hp);
//取堆顶的数据
HPDataType HeapTop(Heap* hp);
//堆的数据个数
int HeapSize(Heap* hp);
//堆的判空
bool HeapEmpty(Heap* hp);
二、实现思路
下部分的图,都以逻辑结构为主!!!
这里构建的是小堆。
1. 结构的定义
堆就是用顺序表来存储一颗完全二叉树,那么堆的结构就与顺序表的结构相同。
一个指向动态开辟空间的指针(data),一个变量记录空间大小(capacity),一个变量记录空间中有效数据(size)。
typedef int HPDataType;
typedef struct Heap
{
HPDataType* data;
int capacity;
int size;
}Heap;
2. 堆的构建 (HeapInit)
malloc一块空间,用data记录其地址,capacity记录此时空间大小,size置0(此时空间内无有效数据)。
//堆的构建
#define SIZE 4
void HeapInit(Heap* hp)
{
assert(hp);
hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);
if (hp == NULL)
{
perror("mallo: ");
exit(-1);
}
hp->capacity = SIZE;
hp->size = 0;
}
3. 堆的销毁 (HeapDestroy)
free掉动态开辟的空间,使capacity 和 size 置 0(此时空间大小为0)
//堆的销毁
void HeapDestroy(Heap* hp)
{
assert(hp);
free(hp->data);
hp->data = NULL;
hp->capacity = hp->size = 0;
}
4. 堆的插入 (HeapPush)
将数据插入到堆的尾部(最后一个子节点后),然后与其父节点相比较,如果该节点小于其父节点(这里是小堆),交换两个节点的值,直到该节点为堆顶或其父节点小于该节点。
- 假设该节点下标是 i,那么其父节点的小标是 ( i - 1 ) / 2
//交换
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向上调整 假设该节点是 i,父节点是 (i - 1) / 2
void AdjustUp(HPDataType* data, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (data[child] < data[parent])
{
swap(&data[child], &data[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//检查容量
if (hp->capacity == hp->size)
{
HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));
if (tmp == NULL)
{
perror("realloc:");
exit(-1);
}
hp->data = tmp;
hp->capacity *= 2;
}
hp->data[hp->size] = x;
hp->size ;
//向上调整 传入数组和出入数据的下标
//此处是小堆
AdjustUp(hp->data, hp->size - 1);
}
5. 堆的删除 (HeapPop)
堆的删除是删除堆顶数据。
堆顶数据和堆的尾部数据交换,size 减一,然后将新的堆顶数据与其左右孩子节点的最小值比较,如果新堆顶数据大于左右孩子节点的最小值,交换数据,再次与新的左右孩子节点的最小值
比较。直到该数据小于左右孩子的最小值,或该数据超出有效数据范围。
- 假设某个节点的下标是 i,其左孩子节点的下标:i * 2 1,其右孩子的下标:i * 2 2
- 删除堆顶数据,不能挪到数据将堆顶数据覆盖。如果挪到数据,那么兄弟节点可能会变成父子节点,而兄弟节点之间并不保证大小关系,可能会破坏堆的结构(这里是会破坏小堆结构)。
//交换
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向下调整,假设该节点是 i, 右孩子节点是 2 * i 1,左孩子节点是 2 * i 2
void AdjustDown(HPDataType* data, int parent, int size)
{
int child = parent * 2 1;
while (parent < size)
{
//防止越界 找左右孩子中最小的
if (child 1 < size && data[child] > data[child 1])
{
child ;
}
if (child < size && data[parent] > data[child])
{
swap(&data[parent], &data[child]);
parent = child;
child = parent * 2 1;
}
else
{
break;
}
}
}
//堆的删除 首元素 与 尾元素交换,新的堆顶在向下调整
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
hp->data[0] = hp->data[hp->size - 1];
hp->size--;
//向下调整
AdjustDown(hp->data, 0, hp->size);
}
6. 取堆顶的数据 (HeapTop)
读取数组空间下标为0处即可。
//取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
return hp->data[0];
}
7. 堆的数据个数 (HeapSize)
堆的结构中size表示此时堆中有效数据的个数,访问size即可。
//堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
8. 堆的判空 (HeapEmpty)
size表示堆的有效数据个数,如果size == 0,表示堆为空。
//堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
三、代码实现
//Heap.c 文件
#include "Heap.h"
//堆的构建
void HeapInit(Heap* hp)
{
assert(hp);
hp->data = (HPDataType*)malloc(sizeof(HPDataType) * SIZE);
if (hp == NULL)
{
perror("mallo: ");
exit(-1);
}
hp->capacity = SIZE;
hp->size = 0;
}
//堆的销毁
void HeapDestroy(Heap* hp)
{
assert(hp);
free(hp->data);
hp->data = NULL;
hp->capacity = hp->size = 0;
}
//交换
void swap(HPDataType* a, HPDataType* b)
{
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
//向上调整 假设该节点是 i,父节点是 (i - 1) / 2
void AdjustUp(HPDataType* data, int child)
{
int parent = (child - 1) / 2;
while (child > 0)
{
if (data[child] < data[parent])
{
swap(&data[child], &data[parent]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
//堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
assert(hp);
//检查容量
if (hp->capacity == hp->size)
{
HPDataType* tmp = (HPDataType*)realloc(hp->data ,sizeof(HPDataType) * (hp->capacity * 2));
if (tmp == NULL)
{
perror("realloc:");
exit(-1);
}
hp->data = tmp;
hp->capacity *= 2;
}
hp->data[hp->size] = x;
hp->size ;
//向上调整 传入数组和出入数据的下标
//此处是小堆
AdjustUp(hp->data, hp->size - 1);
}
//向下调整,假设该节点是 i, 右孩子节点是 2 * i 1,左孩子节点是 2 * i 2
void AdjustDown(HPDataType* data, int parent, int size)
{
int child = parent * 2 1;
while (parent < size)
{
//防止越界 找左右孩子中最小的
if (child 1 < size && data[child] > data[child 1])
{
child ;
}
if (child < size && data[parent] > data[child])
{
swap(&data[parent], &data[child]);
parent = child;
child = parent * 2 1;
}
else
{
break;
}
}
}
//堆的删除 首元素 与 尾元素交换,新的堆顶在向下调整
void HeapPop(Heap* hp)
{
assert(hp);
assert(!HeapEmpty(hp));
hp->data[0] = hp->data[hp->size - 1];
hp->size--;
//向下调整
AdjustDown(hp->data, 0, hp->size);
}
//取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
assert(hp);
return hp->data[0];
}
//堆的数据个数
int HeapSize(Heap* hp)
{
assert(hp);
return hp->size;
}
//堆的判空
bool HeapEmpty(Heap* hp)
{
assert(hp);
return hp->size == 0;
}
//Heap.h 文件
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#define SIZE 4
typedef int HPDataType;
typedef struct Heap
{
HPDataType* data;
int capacity;
int size;
}Heap;
//堆的构建
void HeapInit(Heap* hp);
//堆的销毁
void HeapDestroy(Heap* hp);
//堆的插入
void HeapPush(Heap* hp, HPDataType x);
//堆的删除
void HeapPop(Heap* hp);
//取堆顶的数据
HPDataType HeapTop(Heap* hp);
//堆的数据个数
int HeapSize(Heap* hp);
//堆的判空
bool HeapEmpty(Heap* hp);
总结
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggaia
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13