首页 > 其他 > 详细

堆的代码实现

时间:2021-01-06 22:22:29      阅读:30      评论:0      收藏:0      [点我收藏+]
//假设小堆 typedef int HDataType; typedef struct heap { HDataType* _data; int _size; int _capacity; }heap; void Swap(int* a, int* b) { int tmp = a; a = b; b = tmp; } void heapInit(heap* hp) { if (hp == NULL) return; //空堆 hp->_data = NULL; hp->_size = hp->_capacity = 0; } void heapPush(heap* hp, HDataType val) { checkCapacity(hp); //尾插 hp->_data[hp->_size++] = val; //向上调整 shiftUp(hp->_data, hp->_size, hp->_size - 1); } void hpeaPop(heap* hp) { if (hp->_size > 0) { //交换 Swap(&hp->_data[0], &hp->_data[hp->_size - 1]); hp->_size--; //从堆顶位置向下调整 shiftDown(hp->_data, hp->_size, 0); } } HDataType heapTop(heap* hp) { return hp->_data[0]; } int heapEmpty(heap* hp) { if (hp == NULL || hp->_size == 0) return 1; else return 0; } void checkCapacity(heap* hp) { if (hp->_size = hp->_capacity) { int newC = hp->_capacity == 0 ? 1 : 2 * hp->_capacity; hp->_data = (HDataType*)relloc(hp->_data, sizeof(HDataType)*newC); hp->_capacity = newC; } } /* //向下调整 #include<stdio.h> void shiftDown(int* arr, int n, int cur) { //找到孩子的位置 //左孩子 int child = 2 * cur + 1; while (child < n) { //从左孩子找最小的 if (child + 1 < n&&arr[child] > arr[child + 1]) ++child; //和当前数据做比较 //1.孩子小于当前 调整 if (arr[child] < arr[cur]) { int tmp = arr[child]; arr[child] = arr[cur]; arr[cur] = tmp; //更新位置,继续调整 cur = child; child = 2 * cur + 1; } else //2.孩子>=当前 不调整 break; } } void test() { int arr[] = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 }; int n = sizeof(arr) / sizeof(arr[0]); //建堆:从最后一个非叶子节点开始,向下调整 for (int i = (n - 2) / 2; i >= 0; i--) { shiftDown(arr, n, i); } } //void test() //{ // int arr[] = { 10, 5, 3, 8, 7, 6 }; // shiftDown(arr, sizeof(arr) / sizeof(arr[0]), 0); //} int main() { test(); return 0; }*/

堆的代码实现

原文:https://blog.51cto.com/14982125/2583485

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!