/*===========*\
| binheap.h |
\*===========*/
#ifndef _BINHEAP_H_
#define _BINHEAP_H_
#define ElementType int
#define MinPQSize 2
#define MinData -10000
typedef struct HeapStruct {
int Capacity;
int Size;
ElementType * Elements;
} * PriorityQueue;
//function list
PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue h);
void MakeEmpty(PriorityQueue h);
void Insert(ElementType x,PriorityQueue h);
ElementType DeleteMin(PriorityQueue h);
ElementType FindMin(PriorityQueue h);
int IsEmpty(PriorityQueue h);
int IsFull(PriorityQueue h);
#endif
/*=============*\
| binheap.c |
\*=============*/
#include "binheap.h"
#include <stdio.h>
#include <stdlib.h>
//初始化优先队列
PriorityQueue Initialize(int MaxElements)
{
PriorityQueue h;
if (MaxElements < MinPQSize)
printf("out of space!!\n");
h = (PriorityQueue)malloc(sizeof(struct HeapStruct));
if (h == NULL)
printf("out of space!!\n");
h->Elements = (ElementType *)malloc((MaxElements+1)*sizeof(ElementType));
if (h->Elements == NULL)
printf("out of space!!\n");
h->Capacity = MaxElements;
h->Size = 0;
h->Elements[0] = MinData;
return h;
}
//判断队列是否已满
int IsFull(PriorityQueue h)
{
return h->Size == h->Capacity-1;
}
//判断队列是否为空
int IsEmpty(PriorityQueue h)
{
return h->Size == 0;
}
//插入节点
void Insert(ElementType x,PriorityQueue h)
{
int i ;
if (IsFull(h))
{
printf("Priority queue is full\n");
return;
}
for(i=++h->Size;h->Elements[i/2]>x;i/=2)
h->Elements[i] = h->Elements[i/2];
h->Elements[i]=x;
}
//从节点p下滤
void percolateDown(int p,PriorityQueue h)
{
int i = p;
if (p>h->Size)
{
printf("Out of the size !! : p=%d,size=%d\n",p,h->Size);
return;
}
ElementType element = h->Elements[p];
while (i*2<=h->Size)
{
int minChild = (2*i != h->Size) && (h->Elements[2*i]>h->Elements[2*i+1]) ? 2*i+1 : 2*i;
if(element>h->Elements[minChild])
{
h->Elements[i] = h->Elements[minChild];
i=minChild;
}
else
break;
}
h->Elements[i] = element;
}
//从节点P上滤
void percolateUp(int p,PriorityQueue h)
{
int i;
if (p>h->Size)
{
printf("Out of the size !!\n");
return;
}
ElementType element = h->Elements[p];
for(i=p;h->Elements[i/2]>element;i=i/2)
h->Elements[i] = h->Elements[i/2];
h->Elements[i]=element;
}
//删除最小元
ElementType DeleteMin(PriorityQueue h)
{
int i,Child;
ElementType MinElement,LastElement;
if(IsEmpty(h))
{
printf("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];
else
break;
}
h->Elements[i]=LastElement;
return MinElement;
}
//降低关键字的值
void DecreaseKey(int P,ElementType value,PriorityQueue h)
{
h->Elements[P] -= value;
percolateUp(P,h);
}
//增加关键字的值
void IncreaseKey(int P,ElementType value,PriorityQueue h)
{
h->Elements[P] += value;
percolateDown(P,h);
}
//删除节点
void Delete(int P,PriorityQueue h)
{
DecreaseKey(P,-10000,h);
DeleteMin(h);
}
//构建堆
void BuildHeap(ElementType * et,int n,PriorityQueue h)
{
int i;
h->Size = n;
if (n>h->Capacity)
{
printf("Out of the capacity!\n");
return;
}
for(i=0;i<n;i++)
{
h->Elements[i+1] = et[i];
}
for(i=n/2;i>0;i--)
percolateDown(i,h);
}
//打印二叉堆(优先队列)
void printBinHeap(PriorityQueue h)
{
int i;
for(i=1;i<=h->Size;i++)
printf("%d ",h->Elements[i]);
putchar('\n');
}
//////////////////////////////////////////////////////////////////////////
int main()
{
ElementType a[]={19,18,7,3,4,9,11,22,12};
PriorityQueue h = Initialize(20);
BuildHeap(a,sizeof(a)/sizeof(int),h);
printBinHeap(h);
DecreaseKey(8,20,h);
printBinHeap(h);
IncreaseKey(1,20,h);
printBinHeap(h);
Delete(1,h);
printBinHeap(h);
Insert(3,h);
printBinHeap(h);
system("pause");
return 0;
}
分享到:
相关推荐
多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为10.对n个关键字的序列进行快速排序,平均情况下的空间复杂度为11.在一个单链表中,若删除p结点的后继结点,则执行操作12.为便于判别有向图中是否存在回路...
- 在处理大量顶点时,优先队列的选择(如二叉堆)对算法效率有很大影响。 - 要注意边界条件,例如当图为空或者源点不存在时的处理。 - 对于稠密图和稀疏图,邻接矩阵和邻接表的选用也会对时间和空间复杂度产生影响。...
12.5.1 高度优先与宽度优先的最大及最小左高树 12.5.2 最大HBLT的插入 12.5.3 最大HBLT的删除 12.5.4 两棵最大HBLT的合并 12.5.5 初始化 12.5.6 类maxHblt 12.6 应用 12.6.1 堆排序 12.6.2 机器调度 12.6.3 霍夫曼...
6. **二叉堆与多叉堆**:二叉堆是常用的数据结构,而多叉堆可以有更高的效率,例如三叉堆。虽然多叉堆的高度较低,但某些操作如筛选(downheap)在多叉堆中可以更快。 7. **散列与双向平方试探**:散列是快速查找的...
在处理过程中,可以使用优先队列(如二叉堆)来存储当前找到的最接近点对,以便快速地更新最小距离。 这个过程是递归的,因为对于每个格子,我们都在做相同的事情,即找出其中的最接近点对。递归终止条件是当格子为...
它将输入的数据构造成一个二叉堆,通常是优先队列的一种,然后不断地将堆顶的元素与堆尾的元素交换,接着将堆的尺寸缩小1,并继续调整为新的堆,直到堆的尺寸为1为止。 **工作原理**:堆排序可以分为建堆和排序两个...
创建一个优先队列(如二叉堆),用来存放节点,并根据距离排序。 2. 将源节点插入优先队列。然后进入循环过程,直到队列为空或者找到目标节点。 3. 每次循环,取出距离最小的节点(当前最接近源节点的节点)。假设...
在优先队列章节,讲解了模型、简单的实现、二叉堆、优先队列的应用、d-堆、左式堆、斜堆、二项队列以及标准库中的优先队列实现。排序章节则从预备知识入手,讲解了插入排序、简单排序算法的下界、希尔排序、堆排序、...
小结 练习 参考文献 第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2...
数据结构与算法是计算机科学的基础,本篇作业主要涉及了堆排序、二叉堆、有向图、图的遍历以及最小生成树等概念。以下是针对每个问题的详细解答: 1. 堆排序是一种基于比较的排序算法,它利用了二叉堆的特性。在...
二进制搜索树允许快速查找、插入和删除元素,而二叉堆常用于优先队列的实现,如堆排序。 “链式队列”和“链式栈”都是链表结构的应用,链表可以动态地添加和删除元素,适合处理长度不确定的数据集合。在C语言中,...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 不用链表的散列表5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 标准库中的散列表5.7 可扩散列小结练习参考文献第6章 优先队列(堆)6.1 模型6.2 ...
散列5.1 一般想法5.2 散列函数5.3 分离链接法5.4 开放定址法5.4.1 线性探测法5.4.2 平方探测法5.4.3 双散列5.5 再散列5.6 可扩散列总结练习参考文献第6章 优先队列(堆)6.1 模型6.2 一些简单的实现6.3 二叉堆6.3.1 ...
- 向n个结点的堆中插入一个元素的时间复杂度为O(log2n),因为通常通过调整堆结构(例如二叉堆)来保持堆性质。 7. AVL树: - AVL树是一种自平衡二叉搜索树,每个结点的平衡因子是左右子树的高度差,取值范围是-1...
小结 练习 参考文献第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题...
小结 练习 参考文献第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题...
二叉堆也在这里讲授,还有些附加的材料论述优先队列某些理论上有趣的实现方法。斐波那契堆在第11章讨论,配对堆在第12章讨论。 第7章讨论排序。它特别关注编程细节和分析。讨论并比较所有通用的排序算法。对以下四...
6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 堆的其他操作 6.4 优先队列的应用 6.4.1 选择问题 6.4.2 事件模拟 6.5 d堆 6.6 左式堆 ...
这个算法通过维护一个优先级队列(通常使用二叉堆实现)来存储待探索的节点,优先选择具有最低f值的节点进行扩展。 在这个十五数码程序中,每个状态可以看作是游戏的一个配置,即数字的位置。启发式函数h(n)可能...