文档章节

算法导论复习:第六章

fzyz_sb
 fzyz_sb
发布于 2014/01/02 19:54
字数 916
阅读 26
收藏 0
点赞 0
评论 0

堆排序的优势:与归并排序一样,但不同于插入排序的是,堆排序的时间复杂度为nlgn.而与插入排序相同,但不同于归并排序的是,堆排序同样具有空间原址性:任何时候都只需要常数个额外的元素空间存储临时数据.

1. 维护堆的性质

我们需要将第一张图的堆(不符合最大堆的性质)维护成最后最后一张图的堆:

代码如下:

#include <stdio.h>

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void max_heapify( int *A, int i, int len )
{
	int left = i * 2 + 1;
	int right = i * 2 + 2;
	int largest = 0;
	if ( left <= len && A[ left ] > A[ i ] ){
		largest = left;
	}
	else{
		largest = i;
	}
	if ( right <= len && A[ right ] > A[ largest ] ){
		largest = right;
	}

	if ( largest != i ){
		swap( &A[ i ], &A[ largest ] );
		max_heapify( A, largest, len );
	}
}

int main( void )
{
	int A[ 10 ] = { 16, 4, 10, 14, 7, 9, 3, 2, 8, 1 };
	int i = 0;
	max_heapify( A, 1, 9 );

	for ( i = 0; i < 10; i++ ){
		printf("%d ", A[ i ] );
	}
	printf("\n");

	return 0;
}



程序输出:

2. 建堆

对每个非叶子节点都调用max_heapify即可(要注意下标索引):

#include <stdio.h>

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void max_heapify( int *A, int i, int len )
{
	int left = i * 2 + 1;
	int right = i * 2 + 2;
	int largest = 0;
	if ( left < len && A[ left ] > A[ i ] ){
		largest = left;
	}
	else{
		largest = i;
	}
	if ( right < len && A[ right ] > A[ largest ] ){
		largest = right;
	}

	if ( largest != i ){
		swap( &A[ i ], &A[ largest ] );
		max_heapify( A, largest, len );
	}
}

void build_max_heap( int *A, int len )
{
	int		index = len / 2 - 1;
	for ( ; index >= 0; index-- ){
		max_heapify( A, index, len );
	}
}

int main( void )
{
	int		i = 0;
	int		A[ 10 ];
	for ( i = 0; i < 10; i++ ){
		A[ i ] = i;
	}
	build_max_heap( A, 10 );

	for ( i = 0; i < 10; i++ ){
		printf("%d ", A[ i ] );
	}
	printf("\n");

	return 0;
}



程序输出:

3. 堆排序算法

把最大结点提取出来,然后对新成的堆继续进行维护堆的性质,并且减少其长度.

#include <stdio.h>
#include <time.h>

#define SIZE 100

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void max_heapify( int *A, int i, int len )
{
	int left = i * 2 + 1;
	int right = i * 2 + 2;
	int largest = 0;
	if ( left < len && A[ left ] > A[ i ] ){
		largest = left;
	}
	else{
		largest = i;
	}
	if ( right < len && A[ right ] > A[ largest ] ){
		largest = right;
	}

	if ( largest != i ){
		swap( &A[ i ], &A[ largest ] );
		max_heapify( A, largest, len );
	}
}

void build_max_heap( int *A, int len )
{
	int		index = len / 2 - 1;
	for ( ; index >= 0; index-- ){
		max_heapify( A, index, len );
	}
}

void heapsort( int *A, int len )
{
	int		i = 0;
	build_max_heap( A, len );
	for ( i = len - 1; i >= 1; i-- ){
		swap( &A[ i ], &A[ 0 ] );
		len -= 1;
		max_heapify( A, 0, len );
	}
}

int main( void )
{
	int		A[ SIZE ];
	int		i = 0;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < 100; i++ ){
		A[ i ] = rand() % 100;
	}
	heapsort( A, 100 );

	for ( i = 0; i < 100; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}



程序输出:


4. 优先队列

#include <stdio.h>
#include <time.h>
#include <stdlib.h>


#define SIZE 10

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void max_heapify( int *A, int i, int len )
{
	int left = i * 2 + 1;
	int right = i * 2 + 2;
	int largest = 0;
	if ( left < len && A[ left ] > A[ i ] ){
		largest = left;
	}
	else{
		largest = i;
	}
	if ( right < len && A[ right ] > A[ largest ] ){
		largest = right;
	}

	if ( largest != i ){
		swap( &A[ i ], &A[ largest ] );
		max_heapify( A, largest, len );
	}
}

void build_max_heap( int *A, int len )
{
	int		index = len / 2 - 1;
	for ( ; index >= 0; index-- ){
		max_heapify( A, index, len );
	}
}

void heapsort( int *A, int len )
{
	int		i = 0;
	build_max_heap( A, len );
	for ( i = len - 1; i >= 1; i-- ){
		swap( &A[ i ], &A[ 0 ] );
		len -= 1;
		max_heapify( A, 0, len );
	}
}

int heap_maximum( int *A ){
	return A[ 0 ];
}

int heap_extract_max( int *A, int *len )
{
	int max = INT_MIN;
	if ( *len < 1 ){
		printf("heap underflow");
		return max;
	}
	max = A[ 0 ];
	A[ 0 ] = A[ *len - 1 ];
	*len -= 1;
	max_heapify( A, 0, *len );

	return max;
}

void heap_increase_key( int *A, int len, int key )
{
	int		index = len;
	A[ index ] = key;
	while ( index >= 0 && A[ ( index - 1 ) / 2 ] < A[ index ] ){
		swap( &A[ ( index - 1 ) / 2 ], &A[ index ]);
		index = ( index - 1 ) / 2;
	}
}

int main( void )
{
	int		A[ SIZE ];
	int		i = 0;
	int		len = SIZE;
	srand( ( unsigned int )time( NULL ) );
	for ( i = 0; i < SIZE; i++ ){
		A[ i ] = rand() % SIZE;
	}

	build_max_heap( A, len );

	for ( i = 0; i < SIZE; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");

	printf("max element is:%d\n", heap_maximum( A ) );
	heap_extract_max( A, &len );
	heap_increase_key( A, len, 6 );
	for ( i = 0; i < SIZE; i++ ){
		printf("%d ", A[ i ] );
		if ( 0 == ( i + 1 ) % 10 ){
			printf("\n");
		}
	}
	printf("\n");


	return 0;
}



程序输出:


© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
算法导论复习:第十二章

二叉搜索树的实现: 备注:算法导论中文版第168页中删除节点时候,y=TREEMINIMUM(z.right)是错误的,应该寻找后继结点,为y=TREESUCCESSOR(z.right). #include <stdio.h> include <stdlib.h> inc......

fzyz_sb ⋅ 2014/01/05 ⋅ 0

数据结构算法书籍推荐

学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。在这里列出一些我看过或者准备看的算法书籍,以供参考。 ...

modernizr ⋅ 2014/05/22 ⋅ 13

ACM算法书籍推荐zz

我常感叹到,学计算机的人是幸福的,因为在这个领域中有如此多的通俗易懂(相对来说)的经典好书,你需要做的只是坚持把它们一本一本读下去而已。学力学就没有这样的好事了(抱怨一下),除了...

heartfly ⋅ 2010/10/03 ⋅ 1

算法导论复习:第十三章

红黑树的性质 树中每个节点包含5个属性:color,key,left,right和p.如果一个节点没有子节点或父节点,则该节点相应指针属性的值为NIL. 一棵红黑树是满足下面红黑性质的二叉搜索树: 1). 每个节点...

fzyz_sb ⋅ 2014/01/05 ⋅ 0

算法导论复习:第十章

栈的实现 #include <stdio.h> include <stdlib.h> include <limits.h> define SIZE 100 int stack[ SIZE ];int top = 0;int stackEmpty( int *S );int stackFull( int *S );void push( int *......

fzyz_sb ⋅ 2014/01/04 ⋅ 0

算法导论复习:第二章

插入排序 #include <stdio.h> include <stdlib.h> include <time.h> void insert_sort( int *A, int len ){int i = 0;int j = 0;int key = 0;for ( j = 1; j < len; j++ ){key = A[ j ];i = ......

fzyz_sb ⋅ 2014/01/01 ⋅ 0

算法导论复习:第八章和第九章

定理: 在最坏情况下,任何比较排序算法都需要做nlgn次比较. 1. 计数排序 基本原理:假设n个输入元素中的每一个都是在0到k区间内的一个整数,其中k为某个整数.当k=O(n)时,排序的运行时间为n.对于...

fzyz_sb ⋅ 2014/01/04 ⋅ 0

算法-第四版习题索引汇总

算法-第四版习题索引汇总 持续更新中。。。 第一章 基础 算法-第四版-1.1 基础编程模型-习题索引汇总 算法-第四版-1.2 数据抽象-习题索引汇总 算法-第四版-1.3 背包、队列和栈-习题...

himayan46 ⋅ 2016/09/28 ⋅ 0

数据结构(C语言版)第五章:树

5.2 二叉树 我们写一个二叉树,它支持树的插入,删除,查询和遍历,而且左子树的数据都小于右子树的数据(PS:树实际上很难的,想深入了解的话,可以去看看<算法导论>,什么红黑树啊,B树啊什么的,反正...

fzyz_sb ⋅ 2013/12/07 ⋅ 2

acm核心教材

Introduction to Algorithms:算法导论(4个版本) - Thomas H. Cormen,Charles E. Leiserson 本书是MIT计算机专业的经典算法教材,内容全面,语言通俗,很适合入门者学习 Introductory combina...

齐勇cn ⋅ 2015/04/02 ⋅ 1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从零开始搭建Risc-v Rocket环境---(1)

为了搭建Rocke环境,我买了一个2T的移动硬盘,安装的ubuntu-16.04 LTS版。没有java8,gcc是5.4.0 joe@joe-Inspiron-7460:~$ java -version程序 'java' 已包含在下列软件包中: * default-...

whoisliang ⋅ 26分钟前 ⋅ 0

大数据学习路线(自己制定的,从零开始学习大数据)

大数据已经火了很久了,一直想了解它学习它结果没时间,过年后终于有时间了,了解了一些资料,结合我自己的情况,初步整理了一个学习路线,有问题的希望大神指点。 学习路线 Linux(shell,高并...

董黎明 ⋅ 32分钟前 ⋅ 0

systemd编写服务

一、开机启动 对于那些支持 Systemd 的软件,安装的时候,会自动在/usr/lib/systemd/system目录添加一个配置文件。 如果你想让该软件开机启动,就执行下面的命令(以httpd.service为例)。 ...

勇敢的飞石 ⋅ 34分钟前 ⋅ 0

mysql 基本sql

CREATE TABLE `BBB_build_info` ( `community_id` varchar(50) NOT NULL COMMENT '小区ID', `layer` int(11) NOT NULL COMMENT '地址层数', `id` int(11) NOT NULL COMMENT '地址id', `full_......

zaolonglei ⋅ 43分钟前 ⋅ 0

安装chrome的vue插件

参看文档:https://www.cnblogs.com/yulingjia/p/7904138.html

xiaoge2016 ⋅ 45分钟前 ⋅ 0

用SQL命令查看Mysql数据库大小

要想知道每个数据库的大小的话,步骤如下: 1、进入information_schema 数据库(存放了其他的数据库的信息) use information_schema; 2、查询所有数据的大小: select concat(round(sum(da...

源哥L ⋅ 今天 ⋅ 0

两个小实验简单介绍@Scope("prototype")

实验一 首先有如下代码(其中@RestController的作用相当于@Controller+@Responsebody,可忽略) @RestController//@Scope("prototype")public class TestController { @RequestMap...

kalnkaya ⋅ 今天 ⋅ 0

php-fpm的pool&php-fpm慢执行日志&open_basedir&php-fpm进程管理

12.21 php-fpm的pool pool是PHP-fpm的资源池,如果多个站点共用一个pool,则可能造成资源池中的资源耗尽,最终访问网站时出现502。 为了解决上述问题,我们可以配置多个pool,不同的站点使用...

影夜Linux ⋅ 今天 ⋅ 0

微服务 WildFly Swarm 管理

Expose Application Metrics and Information 要公开关于我们的微服务的有用信息,我们需要做的就是将监视器模块添加到我们的pom.xml中: 这将使在管理和监视功能得到实现。从监控角度来看,...

woshixin ⋅ 今天 ⋅ 0

java连接 mongo伪集群部署遇到的坑

部署mongo伪集群 #创建mongo数据存放文件地址mkdir -p /usr/local/config1/datamkdir -p /usr/local/config2/data mkdir -p /usr/local/config3/data mkdir -p /usr/local/config1/l......

努力爬坑人 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部