邢台建设专业网站,宿州网站建设电话,珠宝网站模版,哈尔滨网站建设论坛个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》 文章目录 一、堆二、实现思路1. 结构的定义2. 堆的构建 (HeapInit)3. 堆的销毁 (HeapDestroy)4. 堆的插入 (HeapPush)5. 堆的删除 (HeapPop)6. 取堆顶的数据 (HeapTop)7. 堆的数据个数 (HeapSize… 个人主页 个人主页 个人专栏 《数据结构》 《C语言》 文章目录 一、堆二、实现思路1. 结构的定义2. 堆的构建 (HeapInit)3. 堆的销毁 (HeapDestroy)4. 堆的插入 (HeapPush)5. 堆的删除 (HeapPop)6. 取堆顶的数据 (HeapTop)7. 堆的数据个数 (HeapSize)8. 堆的判空 (HeapEmpty) 三、代码实现总结 一、堆
当一颗完全二叉树用顺序表来存储时其被称为堆。
堆总是一棵完全二叉树堆的某个节点的值总是不大于(大堆)或不小于(小堆)其父节点的值
其可以被用来解决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 4void 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 4typedef 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); 总结
以上就是我对于堆的实现
