`
hojor
  • 浏览: 109186 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

二叉堆(优先对列)

 
阅读更多
/*===========*\
 | 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;
}

 

分享到:
评论

相关推荐

    东大22春《数据结构Ⅱ》在线平时作业3-00001

    多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为10.对n个关键字的序列进行快速排序,平均情况下的空间复杂度为11.在一个单链表中,若删除p结点的后继结点,则执行操作12.为便于判别有向图中是否存在回路...

    Dijkstra 4组测数据及答案.zip

    - 在处理大量顶点时,优先队列的选择(如二叉堆)对算法效率有很大影响。 - 要注意边界条件,例如当图为空或者源点不存在时的处理。 - 对于稠密图和稀疏图,邻接矩阵和邻接表的选用也会对时间和空间复杂度产生影响。...

    数据结构、算法与应用:C++语言描述(原书第2版)第二部分

    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 霍夫曼...

    DSA真题2014 解答.pdf

    6. **二叉堆与多叉堆**:二叉堆是常用的数据结构,而多叉堆可以有更高的效率,例如三叉堆。虽然多叉堆的高度较低,但某些操作如筛选(downheap)在多叉堆中可以更快。 7. **散列与双向平方试探**:散列是快速查找的...

    平面点集最接近点对源码

    在处理过程中,可以使用优先队列(如二叉堆)来存储当前找到的最接近点对,以便快速地更新最小距离。 这个过程是递归的,因为对于每个格子,我们都在做相同的事情,即找出其中的最接近点对。递归终止条件是当格子为...

    算法小节(排序)6种 低级到高级

    它将输入的数据构造成一个二叉堆,通常是优先队列的一种,然后不断地将堆顶的元素与堆尾的元素交换,接着将堆的尺寸缩小1,并继续调整为新的堆,直到堆的尺寸为1为止。 **工作原理**:堆排序可以分为建堆和排序两个...

    dijkstra算法实现两景点间最短路径.zip

    创建一个优先队列(如二叉堆),用来存放节点,并根据距离排序。 2. 将源节点插入优先队列。然后进入循环过程,直到队列为空或者找到目标节点。 3. 每次循环,取出距离最小的节点(当前最接近源节点的节点)。假设...

    数据结构与算法分析_Java语言描述(第2版)

    在优先队列章节,讲解了模型、简单的实现、二叉堆、优先队列的应用、d-堆、左式堆、斜堆、二项队列以及标准库中的优先队列实现。排序章节则从预备知识入手,讲解了插入排序、简单排序算法的下界、希尔排序、堆排序、...

    数据结构与算法分析_Java_语言描述

    小结 练习 参考文献 第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...

    数据结构及其算法第三次作业.pdf

    数据结构与算法是计算机科学的基础,本篇作业主要涉及了堆排序、二叉堆、有向图、图的遍历以及最小生成树等概念。以下是针对每个问题的详细解答: 1. 堆排序是一种基于比较的排序算法,它利用了二叉堆的特性。在...

    数据结构代码

    二进制搜索树允许快速查找、插入和删除元素,而二叉堆常用于优先队列的实现,如堆排序。 “链式队列”和“链式栈”都是链表结构的应用,链表可以动态地添加和删除元素,适合处理长度不确定的数据集合。在C语言中,...

    数据结构与算法分析Java语言描述(第二版)

    散列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 ...

    数据结构与算法分析第二版 ---C语言描述(附加答案)

    散列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 ...

    中央广播电视大学 数据结构期末考试1

    - 向n个结点的堆中插入一个元素的时间复杂度为O(log2n),因为通常通过调整堆结构(例如二叉堆)来保持堆性质。 7. AVL树: - AVL树是一种自平衡二叉搜索树,每个结点的平衡因子是左右子树的高度差,取值范围是-1...

    数据结构与算法分析-Java语言描述(第2版)_2_2

    小结 练习 参考文献第6章 优先队列(堆) 6.1 模型 6.2 一些简单的实现 6.3 二叉堆 6.3.1 结构性质 6.3.2 堆序性质 6.3.3 基本的堆操作 6.3.4 其他的堆操作 6.4 优先队列的应用 6.4.1 选择问题...

    数据结构与算法分析-Java语言描述(第2版)_1_2

    小结 练习 参考文献第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章讨论排序。它特别关注编程细节和分析。讨论并比较所有通用的排序算法。对以下四...

    数据结构与算法分析C描述第三版

     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 左式堆   ...

    基于A*算法的十五数码程序 C语言版

    这个算法通过维护一个优先级队列(通常使用二叉堆实现)来存储待探索的节点,优先选择具有最低f值的节点进行扩展。 在这个十五数码程序中,每个状态可以看作是游戏的一个配置,即数字的位置。启发式函数h(n)可能...

Global site tag (gtag.js) - Google Analytics