文档章节

算法导论复习:第六章

fzyz_sb
 fzyz_sb
发布于 2014/01/02 19:54
字数 916
阅读 26
收藏 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
粉丝 408
博文 209
码字总数 447144
作品 0
武汉
程序员
数据结构算法书籍推荐

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

modernizr
2014/05/22
28.1K
13
算法-第四版习题索引汇总

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

himayan46
2016/09/28
0
0
数据结构(C语言版)第五章:树

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

fzyz_sb
2013/12/07
0
2
ZOJ 3499. Median

    地址:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4322     题意:寻找中位数。对于一个(浮点数)数组,如果含有奇数个元素,“中位数”就是排序后位于数组中...

hoodlum1980
2012/06/13
0
0
BAT等大厂Android面试书单和知识点清单

java是Android开发的基础,在BAT的初面中,会涉及到比较多的java基础知识,所以比较重要,下面我介绍的书籍内容是由浅到深。 1.Thinking in java:这本书被称为Java的三大圣经之一,虽然书比...

android自学
07/25
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
59分钟前
0
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0
memcached命令行、memcached数据导出和导入

一、memcached命令行 yum装telnet yum install telent 进入memcached telnet 127.0.0.1 11211 命令最后的2表示,两位字节,30表示过期时间(秒) 查看key1 get key1 删除:ctrl+删除键 二、m...

Zhouliang6
今天
0
0
Linux定时备份MySQL数据库

做项目有时候要备份数据库,手动备份太麻烦,所以找了一下定时备份数据库的方法 Linux里有一个 crontab 命令被用来提交和管理用户的需要周期性执行的任务,就像Windows里的定时任务一样,用这...

月夜中徘徊
今天
1
1

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部