首页 > 使用最小堆使用优先级队列(c语言版本)

使用最小堆使用优先级队列(c语言版本)

下面的例子来自Weiss的《数据结构与算法分析：c语言描述》，自己亲自敲了一遍，跑了个demo，并将结果记录下来。

binheap.h的头文件声明

//description: 使最小堆实现优先级队列
//date: 2019-03-15#ifndef __BINHEAP_H__
#define __BINHEAP_H__typedef int ElementType;struct HeapStruct {int Capacity; //最大容量int Size; //当前大小ElementType *Elements; //元素数组
};typedef struct HeapStruct *PriorityQueue;PriorityQueue Initialize(int MaxElements);void Destroy(PriorityQueue H);void MakeEmpty(PriorityQueue H);int IsEmpty(PriorityQueue H);int IsFull(PriorityQueue H);void Insert(ElementType X, PriorityQueue H);ElementType DeleteMin(PriorityQueue H);ElementType FindMin(PriorityQueue H);#endif

binheap.c源码文件

#include "binheap.h"
#include 
#include #define MinData (-32767)
#define MinPQSize (10)PriorityQueue
Initialize(int MaxElements){PriorityQueue H;if(MaxElements < MinPQSize){printf("Priority queue size is too small");exit(-1);}H = malloc(sizeof(struct HeapStruct));if(H == NULL){printf("failed to alloc memory space for HeapStruct");exit(-1);}/* allocate the array plus one extra for sentinel  */H->Elements = malloc( (MaxElements+1) * sizeof(ElementType));if(H->Elements == NULL){printf("failed to allocate memory for Elements array");exit(-1);}H->Capacity = MaxElements;H->Size = 0;H->Elements[0] = MinData; //此处设置哨兵return H;
}void
Destroy(PriorityQueue H){free(H->Elements);free(H);
}void
MakeEmpty(PriorityQueue H){H->Size = 0;
}void
Insert(ElementType X, PriorityQueue H){int i;if(IsFull(H)){printf("Priority queue is full");return;}//从尾部向头部检查for(i=++H->Size; H->Elements[i/2]>X; i/=2){H->Elements[i] = H->Elements[i/2];}H->Elements[i] = X;
}ElementType
DeleteMin(PriorityQueue H){int i,Child;ElementType MinElement, LastElement;if(IsEmpty(H)){printf("FATAL: Priority queue is empty");return H->Elements[0];}MinElement = H->Elements[1];LastElement = H->Elements[H->Size--];for(i=1; i * 2 <= H->Size; i=Child){/*Find smaller child*/Child = i * 2;if(Child != H->Size && H->Elements[Child+1] < H->Elements[Child])Child++;/*Percolate one level *///此时最后一个元素已经在堆顶部了，头部与最后一个元素交换过了if(LastElement > H->Elements[Child])H->Elements[i] = H->Elements[Child];elsebreak;}H->Elements[i] = LastElement;return MinElement;
}ElementType
FindMin(PriorityQueue H){if(!IsEmpty(H))return H->Elements[1];printf("FATAL: Priority queue is Empty");return H->Elements[0];
}int
IsEmpty(PriorityQueue H){return H->Size == 0;
}int
IsFull(PriorityQueue H){return H->Size == H->Capacity;
}//=================================
int main(){int i, NUM=30;PriorityQueue pq = Initialize(NUM);for(i=0; i

下面是运行图示：

更多相关：

  • java 读取excel_Java12POI操作Excel

            Apache POI是一个开源的利用Java读写Excel，WORD等微软OLE2组件文档的项目。        我的需求是对Excel的数据进行导入或将数据以Excel的形式导出。先上简单的测试代码：package com.xing.studyTest.poi;import java.io.FileInputSt...

  • C++ 生成随机数

    要取得[a,b)的随机整数，使用(rand() % (b-a))+ a; 要取得[a,b]的随机整数，使用(rand() % (b-a+1))+ a; 要取得(a,b]的随机整数，使用(rand() % (b-a))+ a + 1; 通用公式:a + rand() % n；其中的a是起始值，n是整数的范围。 要取得a到b之间的...

  • 基于C++的本征图像分解(Intrinsic Image Decomposition)

    利用本征图像分解(Intrinsic Image Decomposition)算法，将图像分解为shading(illumination) image 和 reflectance(albedo) image，计算图像的reflectance image。 Reflectance Image 是指在变化的光照条件下能够维持不变的图像部分...

  • 剑指offer：面试题39. 数组中出现次数超过一半的数字

    题目：面试题39. 数组中出现次数超过一半的数字 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。 你可以假设数组是非空的，并且给定的数组总是存在多数元素。 示例 1: 输入: [1, 2, 3, 2, 2, 2, 5, 4, 2] 输出: 2 限制： 1 <= 数组长度 <= 50000 解题： cl...

  • 剑指offer：面试题33. 二叉搜索树的后序遍历序列

    题目：二叉搜索树的后序遍历序列 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是则返回 true，否则返回 false。假设输入的数组的任意两个数字都互不相同。 参考以下这颗二叉搜索树：      5     /    2   6   /  1   3示例 1： 输入: [1,6,3,2,5] 输出...

©2024 11GX.COM