`
xitongyunwei
  • 浏览: 916207 次
文章分类
社区版块
存档分类
最新评论

二叉堆例程

 
阅读更多

二叉堆是一种优先队列的数据结构,具有2种性质:结构性质堆序性。这里讨论都基于最小二叉堆,这种二叉堆对最小元素的访问非常高效。

二叉堆的ADT操作主要包括Insert(插入)和DeleteMin(删除最小元)。

1、结构性质:堆是一棵完全二叉树(若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 都被填满,第 h 层所有的结点都连续集中在最左边),如下图。


(1)因为完全二叉树很有规律,因此可以用一个数组而不需要用指针存储,可以存储成如下形式,其中[0]地址处元素常常用于标记(对于最小二叉堆而言,存储一个非常小的值),这只是为了编程方便,当然也可以不用该标记。


(2)对于数组中任一位置i处的元素,其左儿子在位置2*i上,右儿子在2*i+1上。这条信息很有用,也正因为这样,我们可以很方便的不用指针而只用数组就能访问左右儿子。

2、堆序性:

由于我们想快速的找到最小元,因此最小元应在根上。我们可以以O(1)时间找到最小值。

堆序性指,在一个堆中,每一个节点X,X父亲中的关键字小于(或等于)X中的关键字,根节点除外(因为没有父亲)。


3、插入

为将一个元素 X 插入到堆中,我们在下一个可用位置创建一个空穴,否则该堆将不是完全数。如果 X 可以放在该空穴中而不破坏堆的序,那么插入完成。否则,我们把空穴的父节点上的元素移入该空穴中,这样,空穴就朝着根的方向上冒一步。继续改过程直到 X 能被放入空穴中为止。



这样一般的策略叫做上滤( percolate up);新元素在堆中上滤直到找出正确的位置。

4、删除最小元

当删除一个最小元时,要在根节点建立一个空穴。由于现在堆少了一个元素,因此堆中最后一个元素 X 必须移动到该堆的某个地方。如果 X 可以直接被放到空穴中,那么 deleteMin 完成。不过这一般不太可能,因此我们将空穴的两个儿子中比较小者移入空穴,这样就把空穴向下推了一层。重复该步骤直到 X 可以被放入空穴中。因此,我们的做法是将 X 置入沿着从根开始包含最小儿子的一条路径上的一个正确的位置。



这种一般的策略叫做下滤(percolate down)。

5、程序代码实例

BinHeap.h(types.h中只是些重定义)

/*
 * =====================================================================================
 *
 *       Filename:  BinHeap.h
 *
 *    Description:  二叉堆上滤和下滤的例程
 *
 *        Version:  1.0
 *        Created:  2012/12/2 19:20:45
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xhzuoxin (QQ:1126804077), xiahouzuoxin@163.com
 *   Organization:  
 *
 * =====================================================================================
 */
#ifndef _BINHEAP_H
#define _BINHEAP_H

#include "../types.h"

typedef UINT16 EleType;
typedef struct HeapStruct
{
	int cur;
	int size;
	EleType *ele;
}Heap;
typedef Heap* PtrHeap;
typedef UINT16 Position;

/* functions */
extern PtrHeap InitHeap(PtrHeap h, int max_ele);
extern PtrHeap InsertHeap(PtrHeap h, EleType x);
extern EleType DelMinHeap(PtrHeap h);
extern PtrHeap BuildHeap(EleType *x, int n);
extern PtrHeap DecreaseKey(Position pos, int delta, PtrHeap h);
extern PtrHeap IncreaseKey(Position pos, int delta, PtrHeap h);
extern EleType Delete(Position pos, PtrHeap h);

#endif

BinHeap.c

/*
 * =====================================================================================
 *
 *       Filename:  BinHeap.c
 *
 *    Description:  
 *
 *        Version:  1.0
 *        Created:  2012/12/2 20:17:44
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xhzuoxin (QQ:1126804077), xiahouzuoxin@163.com
 *   Organization:  
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include "BinHeap.h"          

#define ERR_MSG(x)              printf(x)
#define MIN_DATA                (0)


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  PercolateDown
 *  Description:  空穴下滤操作
 * =====================================================================================
 */
static void PercolateDown(PtrHeap h, UINT16 hole)
{
	UINT16 i = 0;
	UINT16 child = 0;
	EleType temp = 0;

	if(NULL == h)
	{
		return;
	}

	temp = h->ele[hole];
	i = hole;
	child = 2 * i;
	while(child <= h->cur)
	{
		if(child != h->cur)    // have left+right child
		{
			if(h->ele[child+1] < h->ele[child])
			{
				child = child + 1;
			}
		}

		// compare to h->ele[hole]
		if(temp > h->ele[child])
		{
			h->ele[i] = h->ele[child];
		}
		else
		{
			break;
		}

		i = child;
		child = 2 * i;
	}
	h->ele[i] = temp;
} 


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  PercolateUp
 *  Description:  上滤操作
 * =====================================================================================
 */
static void PercolateUp(PtrHeap h, UINT16 hole)
{
	EleType temp = h->ele[hole];
	UINT16 i = 0;
	UINT16 parent = 0;

	i = hole;
	parent = i >> 1;
	while(temp < h->ele[parent])
	{
		h->ele[i] = h->ele[parent];
		i = parent;
		parent = i >> 1;
	}
	h->ele[i] = temp;
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  InitHeap
 *  Description:  
 * =====================================================================================
 */
PtrHeap InitHeap(PtrHeap h, int max_ele)
{
	if(h != NULL)
	{
		if(h->ele != NULL)
		{
			free(h->ele);
		}
		free(h);
	}

	h = (PtrHeap)malloc(sizeof(Heap));
	if(NULL == h)
	{
		ERR_MSG("out of space!\n");
		return NULL;
	}

	h->ele = (EleType *)malloc(max_ele*sizeof(EleType));
	if(NULL == h->ele)
	{
		ERR_MSG("out of space!\n");
		return NULL;
	}

	h->size = max_ele;
	h->cur = 0;
	h->ele[0] = MIN_DATA;

	return h;
}


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  InsertHeap
 *  Description:  insert is a percolate up operator
 * =====================================================================================
 */
PtrHeap InsertHeap(PtrHeap h, EleType x)
{
	int i = 0;

	if(h->cur >= h->size-1)
	{
		ERR_MSG("Heap is full!\n");
		return NULL;
	}

	for(i = ++h->cur; h->ele[i>>1] > x; i >>= 1)
	{
		h->ele[i] = h->ele[i>>1];
	}
	h->ele[i] = x;

	return h;
}


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  DelMinHeap
 *  Description:  
 * =====================================================================================
 */
EleType DelMinHeap(PtrHeap h)
{
	int i = 0;
	int child = 0;
	EleType min_ele, last_ele;

	if(h->cur == 0)     /* empty heap */
	{
		ERR_MSG("Heap is empty!\n");
		return h->ele[0];
	}	

	min_ele = h->ele[1];
	
	last_ele = h->ele[h->cur];
	h->cur--;

	i = 1;
	child = 2 * i;
	while(child <= h->cur)
	{
		if((child < h->cur) && (h->ele[child+1] < h->ele[child]))
		{
			child++;
		}
		/* compare to last_element */
		if(h->ele[child] < last_ele)
		{
			h->ele[i] = h->ele[child];
		}
		else
		{
			break;
		}

		i = child;
		child = 2 * i;
	}
	h->ele[i] = last_ele;
	
	return min_ele;
}


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  BuildHeap
 *  Description:  从数组中建立堆的例程
 * =====================================================================================
 */
PtrHeap BuildHeap(EleType *x, int n)
{
	PtrHeap h = NULL;
	int i = 0;

	h = InitHeap(h, n*2);      /* include ele[0]=0 */
	for(i=0; i<n; i++)
	{
		h->ele[i+1] = x[i];
	}

	h->cur = n;
	for(i=n/2; i>0; i--)
	{
		PercolateDown(h, i);		
	}

	return h;
}


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  IncreaseKey
 *  Description:  增加关键字的值
 *                pos -- 关键字在堆中的位置
 *                delta -- 增幅
 *                h -- 堆
 * =====================================================================================
 */
PtrHeap IncreaseKey(Position pos, int delta, PtrHeap h)
{
	// increase pos
	h->ele[pos] += delta;
	
	PercolateDown(h, pos);

	return h;        // also needn't this line
}

/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  DecreaseKey
 *  Description:  降低关键字的值
 *                pos -- 关键字在堆中的位置
 *                delta -- 降幅
 *                h -- 堆 
 * =====================================================================================
 */
PtrHeap DecreaseKey(Position pos, int delta, PtrHeap h)
{
	// decrease pos
	h->ele[pos] -= delta;

	PercolateUp(h, pos);

	return h;
}


/* 
 * ===  FUNCTION  ======================================================================
 *         Name:  Delete
 *  Description:  Delete a element in Heap.
 *                First, use DecreaseKey(P, Infinite, H);
 *                Second, use DeleteMin(H)
 * =====================================================================================
 */
EleType Delete(Position pos, PtrHeap h)
{
	EleType temp = h->ele[pos];

	DecreaseKey(pos, h->ele[pos], h);     // set ele[POS] want to delete to 0
	if(0 != DelMinHeap(h))
	{
		return 0;
	}

	return temp;
}

TestSuite.c(使用了CUnit的测试文件)

/*
 * =====================================================================================
 *
 *       Filename:  TestSuite.c
 *
 *    Description:  test file
 *
 *        Version:  1.0
 *        Created:  2012/12/3 14:03:34
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  xhzuoxin (QQ:1126804077), xiahouzuoxin@163.com
 *   Organization:  
 *
 * =====================================================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include "CUnit/Console.h"
#include "BinHeap.h"

PtrHeap h = NULL;

int InitSuite(void)
{
	if(NULL == (h=InitHeap(h, 30)))
	{
		return -1;
	}
	else
	{
		return 0;
	}
	return 0;
}

int EndSuite(void)
{
	free(h->ele);
	free(h);

	return 0;
}

void TestInsertHeap(void)
{
	int i = 0;

	if(NULL != h)
	{
		CU_ASSERT(NULL != InsertHeap(h, 50));
		CU_ASSERT(NULL != InsertHeap(h, 100));
		CU_ASSERT(NULL != InsertHeap(h, 200));
	}
	printf("\n	InsertHeap: ");
	for(i=1; i<=h->cur; i++)
	{
		printf("%d ", h->ele[i]);
	}
}

void TestDelMinHeap(void)
{
	printf("\n	DelMin: ");
	while(h->cur > 0)
	{
		printf("%d ", DelMinHeap(h));
	}
}

void TestBuildHeap(void)
{
	int i = 0;

	EleType x[15] = {10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2};
	h = BuildHeap(x, 15);
	printf("\n	BuildHeap:");
	for(i=1; i<=h->cur; i++)
	{
		printf("%d ", h->ele[i]);
	}

}

void TestIncreaseKey(void)
{
	int pos = 5;
	int delta = 50;
	int i = 0;

	h = IncreaseKey(pos, delta, h);
	printf("\n	IncreaseKey:");
	for(i=1; i<=h->cur; i++)
	{
		printf("%d ", h->ele[i]);
	}
}

void TestDecreaseKey(void)
{
	int pos = 5;
	int delta = 1;
	int i = 0;

	h = DecreaseKey(pos, delta, h);
	printf("\n	DecreaseKey:");
	for(i=1; i<=h->cur; i++)
	{
		printf("%d ", h->ele[i]);
	}
}

void TestDelete(void)
{
	int pos = 5;

	EleType e = Delete(pos, h);
	printf("\n	Delete: %d", e);
}

int main(void)
{
//	CU_pSuite suite = NULL;
//
//	/* Init registry */
//	if(CUE_SUCCESS != CU_initialize_registry())
//	{
//		return CU_get_error();
//	}
//	
//	/* add suite */
//	suite = CU_add_suite("suite1", InitSuite, EndSuite);
//	if(NULL == suite)
//	{
//		CU_cleanup_registry();
//		return CU_get_error();
//	}
//
//	/* add tests */
//	if(NULL == CU_add_test(suite, "test of InsertHeap()", TestInsertHeap)
//	|| NULL == CU_add_test(suite, "test of DelMinHeap()", TestDelMinHeap))
//	{
//		CU_cleanup_registry();
//		return CU_get_error();
//	}
//
//	/* run */
//	CU_console_run_tests();
//
//	/* cleanup */
//	CU_cleanup_registry();


	CU_TestInfo testcase[] = {
		{"TestBuild", TestBuildHeap},
		{"TestInsert", TestInsertHeap},
		{"TestIncreaseKey", TestIncreaseKey},
		{"TestDecreaseKey", TestDecreaseKey},
		{"TestDelete", TestDelete},
		{"TestDelMin", TestDelMinHeap},
		CU_TEST_INFO_NULL
	};
	CU_SuiteInfo suite[] = {
		{"Testing func ", InitSuite, EndSuite, testcase},
		CU_SUITE_INFO_NULL
	};

	/* Init registry */
	if(CUE_SUCCESS != CU_initialize_registry())
	{
		return CU_get_error();
	}

	/* register suite */
	if(CUE_SUCCESS != CU_register_suites(suite))
	{
		return 1;
	}

	CU_console_run_tests();

	CU_cleanup_registry();

	return 0;
}


上面程序中不仅包含了堆的Insert和DeleteMin操作,还有BuildHeap的操作。虽然,BuildHeap能使用多次插入操作完成,但我们一般不这么做,一般使用下滤的方法(如下图),详细描述可参考《数据结构与算法——C语言描述》一书。开始将 N 项以任意顺序放入树中,保持结构特性。此时,如果 percolateDown( i ) 从节点 i 下滤,那么 buildHeap 程序则可以由构造方法用于创建一棵堆序的树。


图6-15中的第一棵树是无序树。从图6-15到图6-18中其余7棵树表示出 7 个 percolateDown 中每一个的执行结果。每条虚线对应两次比较:一次是找出较小的儿子节点,另一个是较小的儿子与该节点的比较。注意,在整个算法中只有 10 跳虚线,它们对应 20 次比较。

最终,使用gcc编译的makfile文件为

SRC=BinHeap.c BinHeap.h TestSuite.c
LIB=-L/usr/local/lib
INC=-I/usr/local/include

TestSuite:$(SRC)
	gcc $^ -o $@ $(LIB) $(INC) -lcunit -g -Wall -static 
.PHONY:clean tags
clean:
	rm -f TestSuite *~
tags:
	ctags -R --c++-kinds=+p --fields=+iaS --extra=+q

测试结果如下(正确):


测试案列运行过程:

(1)使用BuildHeap建立堆;

(2)尝试插入元素(50,100,200)到堆;

(3)增加pos=5处的关键字值;

(4)减小pos=5处关键字的值;

(5)Delete函数删除pos=5处的关键字值;

(6)逐个删除最小元直到堆为空


参考:

(1)《数据结构与算法分析——C语言描述》

(2)http://blog.csdn.net/gqltt/article/details/7718484

(3)http://program.sinaapp.com/?p=49计算机程序设计艺术*算法交流



分享到:
评论

相关推荐

    易语言寻路 FindPath ( 源码+例程 )

    易语言寻路 FindPath ( 源码+例程 )。增加了地形属性.@≠。Tags:易语言寻路FindPath源码例程。

    数据结构与算法分析_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...

    数据结构与算法分析第二版 ---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 ...

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

    优先队列(堆)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 事件模拟6.5 d-堆6.6 左式堆6.6.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 选择问题...

    数据结构与算法分析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 左式堆   ...

    数据结构与算法研究(强烈推荐)

    二叉堆也在这里讲授,还有些附加的材料论述优先队列某些理论上有趣的实现方法。斐波那契堆在第11章讨论,配对堆在第12章讨论。 第7章讨论排序。它特别关注编程细节和分析。讨论并比较所有通用的排序算法。对以下四...

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

    优先队列(堆)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 事件模拟6.5 d-堆6.6 左式堆6.6.1 左式堆性质6.6.2 ...

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

    优先队列(堆)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 事件模拟6.5 d-堆6.6 左式堆6.6.1 左式堆性质6.6.2 ...

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

    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 左式堆 6.6.1 左式堆性质 6.6.2 左式堆操作 6.7 斜堆 6.8 二...

    数据结构与算法分析

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

    Delphi算法与数据结构 源码(上)

    4.1比较例程 4.2顺序查找 4.3二分查找 4.4小结 第5章排序 5.1排序算法 5.2排序基础知识 5.3小结 第6章随机算法 6.1随机数生成 6.2其他随机数分布 6.3跳表 6.4小结 第7章散列和散列表 7.1散列函数 7.2...

    Delphi算法与数据结构 源码(下)

    4.1比较例程 4.2顺序查找 4.3二分查找 4.4小结 第5章排序 5.1排序算法 5.2排序基础知识 5.3小结 第6章随机算法 6.1随机数生成 6.2其他随机数分布 6.3跳表 6.4小结 第7章散列和散列表 7.1散列函数 7.2...

    Java数据结构和算法中文第二版

    附录中则提供了运行专题Applet和例程、相关书籍和问题解答。本书提供了学完一门编程语言后进一步需要知道的知识。本书所涵盖的内容通常作为大学或学院中计算机系二年级的课程,在学生掌握了编程的基础后才开始本书的...

    程序员实用算法——源码

     6.1.4 二叉查找树的性能  6.1.5 AVL树  6.2 红黑树  6.3 伸展树  6.4 B树  6.4.1 保持B树平衡  6.4.2 实现B树算法  6.4.3 B树实现的代码  6.5 可以看见森林吗  6.6 资源和参考资料 第7章 日期...

    200个经典C程序源码(包括基础篇+数据结构篇+数值计算与趣味数学篇+图形篇+系统篇+常见试题解答篇).zip

    050 二叉搜索树操作 051 二项式系数递归 052 背包问题 053 顺序表插入和删除 054 链表操作(1) 055 链表操作(2) 056 单链表就地逆置 057 运动会分数统计 058 双链表 059 约瑟夫环 060 记录个人资料 ...

Global site tag (gtag.js) - Google Analytics