算法导论复习:第六章
博客专区 > fzyz_sb 的博客 > 博客详情
算法导论复习:第六章
fzyz_sb 发表于4年前
算法导论复习:第六章
  • 发表于 4年前
  • 阅读 15
  • 收藏 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;
}



程序输出:


标签: 数据结构 C
共有 人打赏支持
粉丝 354
博文 209
码字总数 447144
×
fzyz_sb
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: