文档章节

数据结构(C语言版)第九章:堆结构

fzyz_sb
 fzyz_sb
发布于 2013/12/16 22:50
字数 5065
阅读 287
收藏 9
点赞 0
评论 0

9.1 最小-最大堆

双端优先队列是一种支持如下操作的数据结构:

1. 插入一个具有任意关键字值的元素.

2. 删除关键字值最大的元素.

3. 删除关键字值最小的元素.

当仅支持插入和其中的一种删除操作时,可以采用最大堆或者最小堆.而最小-最大堆可以同时支持上述全部操作.

定义:最小-最大堆是一个满足如下条件的完全二叉树:该二叉树不为空,其上的每个元素都有一个称为关键字的域.二叉树的各层交替为最小层和最大层,且根结点位于最小层.设x是最小-最大堆的任意一个节点,如果x位于最小层,那么x就是以x为根结点的二叉树中关键字最小的结点,称该结点为最小结点.类似地,如果x位于最大层,那么x就是以x为根结点的二叉树中关键字值最大的结点,称该结点为最大结点.

9.1.2 最小-最大堆插入

#include <stdio.h>
#include <math.h>
#include <string.h>

#define MAX_SIZE 100

//备注:这里下标从1开始

void swap( int *px, int *py );
/*最小-最大堆的插入*/
void min_max_insert( int heap[], int len, int item );
/*判断父结点是在最小堆还是最大堆,若是最小堆返回0,最大堆返回1*/
int level( int parent );
/*从最大结点开始查找合适位置*/
void verify_max( int heap[], int i, int item );
/*从最小结点开始查找合适位置*/
void verify_min( int heap[], int i, int item );

int main( void )
{
	int arr[ MAX_SIZE ];
	int len = 0;
	int i = 0;
	memset( arr, 0, sizeof( int ) * MAX_SIZE );

	len += 1;
	min_max_insert( arr, len, 7 );
	len += 1;
	min_max_insert( arr, len, 70 );
	len += 1;
	min_max_insert( arr, len, 40 );
	len += 1;
	min_max_insert( arr, len, 30 );
	len += 1;
	min_max_insert( arr, len, 9 );
	len += 1;
	min_max_insert( arr, len, 10 );
	len += 1;
	min_max_insert( arr, len, 15 );
	len += 1;
	min_max_insert( arr, len, 45 );
	len += 1;
	min_max_insert( arr, len, 50 );
	len += 1;
	min_max_insert( arr, len, 30 );
	len += 1;
	min_max_insert( arr, len, 20 );
	len += 1;
	min_max_insert( arr, len, 12 );
	len += 1;
	min_max_insert( arr, len, 5 );

	for ( i = 0; i <= len; i++ ){
		printf("%d ", arr[ i ] );
		if ( 0 == ( i + 1 ) % 5 ){
			printf("\n");
		}
	}

	printf("\n");

	return 0;
}

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}

void min_max_insert( int heap[], int len, int item )
{
	int parent;
	if ( MAX_SIZE == len ){
		fprintf( stderr, "the heap is full\n" );
		return;
	}

	parent = len / 2;
	if ( !parent ){
		heap[ 1 ] = item;
	}
	else{
		switch( level( parent ) ){
			case 0:
				if ( item < heap[ parent ] ){
					heap[ len ] = heap[ parent ];
					verify_min( heap, parent, item );
				}
				else{
					verify_max( heap, len, item );
				}
				break;
			case 1:
				if ( item > heap[ parent ] ){
					heap[ len ] = heap[ parent ];
					verify_max( heap, parent, item );
				}
				else{
					verify_min( heap, len, item );
				}
		}
	}
}

int level( int parent )
{
	return (int)( log( parent ) / log( 2 ) ) % 2;
}

void verify_max( int heap[], int i, int item )
{
	int grandparent = i / 4;
	while ( grandparent ){
		if ( item > heap[ grandparent ] ){
			heap[ i ] = heap[ grandparent ];
			i = grandparent;
			grandparent /= 4;
		}
		else{
			break;
		}
	}
	heap[ i ] = item;
}

void verify_min( int heap[], int i, int item )
{
	int grandparent = i / 4;
	while ( grandparent ){
		if ( item < heap[ grandparent ] ){
			heap[ i ] = heap[ grandparent ];
			i = grandparent;
			grandparent /= 4;
		}
		else{
			break;
		}
	}

	heap[ i ] = item;
}



程序输出:

这里分析不太好弄.书上可以通过画图来解释.所以这里简单解释一下代码中各个函数的作用:

1. level函数:判断parent是在最小层还是在最大层

2. verify_max:从最大层开始执行查找.

3. verify_min:从最小层开始执行查找.

所以,如果一个要插入的节点的父节点为最小层,而本身又小于父节点,则需要执行以下操作:

这样就可以保证从最小层开始执行查找.

插入节点实现了双端队列的第一条性质:插入一个具有任意关键字值的元素.

现在我们来实现剩余的两条性质:1. 删除关键字值最大的元素和删除关键字值最小的元素.

int delete_min( int heap[], int len )
{
	int i, last, k, parent;
	int x;
	if ( !len ){
		fprintf( stderr, "the heap is empty\n" );
		return INT_MAX;
	}
	heap[ 0 ] = heap[ 1 ];
	x = heap[ len-- ];
	for ( i = 1, last = len / 2; i <= last; ){
		k = min_child_grandchild( heap, i, len );
		/*新的根节点为最小结点*/
		if ( x <= heap[ k ] ){
			break;
		}
		heap[ i ] = heap[ k ];
		if ( k <= 2 * i + 1 ){
			i = k;
			break;
		}
		parent = k / 2;
		if ( x > heap[ parent ] ){
			swap( &heap[ parent ], &x );
		}
		i = k;
	}
	heap[ i ] = x;
	return heap[ 0 ];
}

int min_child_grandchild( int arr[], int parent, int len )
{
	int min_value = INT_MAX;
	int i = 2 * parent;
	int min_index = 0;
	for ( ; i <= len; i++ ){
		if ( arr[ i ] < min_value ){
			min_value = arr[ i ];
			min_index = i;
		}
	}

	return min_index;
}

删除最大结点:

int delete_max( int arr[], int len )
{
	int max_index = 0;
	int i, x, last, k, parent;
	if ( !len ){
		fprintf( stderr, "the heap is empty\n" );
		return INT_MAX;
	}
	if ( arr[ 2 ] > arr[ 3 ] ){
		arr[ 0 ] = arr[ 2 ];
		max_index = 2;
	}
	else{
		arr[ 0 ] = arr[ 3 ];
		max_index = 3;
	}
	x = arr[ len-- ];
	for ( i = max_index, last = len / 2; i <= last ; ){
		k = max_child_grandchild( arr, i, len );
		if ( x >= arr[ k ] ){
			break;
		}
		arr[ i ] = arr[ k ];
		if ( k <= 2 * i + 1 ){
			i = k;
			break;
		}
		parent = k / 2;
		if ( x < arr[ parent ] ){
			swap( &arr[ parent ], &x );
		}
		i = k;
	}

	arr[ i ] = x;
	return arr[ 0 ];
}

int max_child_grandchild( int arr[], int parent, int len )
{
	int max_value = INT_MIN;
	int i = 2 * parent;
	int max_index = 0;
	for ( ; i <= len; i++ ){
		if ( arr[ i ] > max_value ){
			max_value = arr[ i ];
			max_index = i;
		}
	}

	return max_index;
}



整个程序如下:

#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>

#define MAX_SIZE 100

//备注:这里下标从1开始

void swap( int *px, int *py );
/*最小-最大堆的插入*/
void min_max_insert( int heap[], int len, int item );
/*判断父结点是在最小堆还是最大堆,若是最小堆返回0,最大堆返回1*/
int level( int parent );
/*从最大结点开始查找合适位置*/
void verify_max( int heap[], int i, int item );
/*从最小结点开始查找合适位置*/
void verify_min( int heap[], int i, int item );

/*删除最小关键字值结点*/
int delete_min( int heap[], int len );
/*确定parent结点的所有儿子和后代结点中关键字值最小的结点*/
int min_child_grandchild( int arr[], int parent, int len );

/*删除最大关键字值结点*/
int delete_max( int heap[], int len );
/*确定parent结点的所有儿子和后代结点中关键字值最大的结点*/
int max_child_grandchild( int arr[], int parent, int len );

int main( void )
{
	int arr[ MAX_SIZE ];
	int len = 0;
	int i = 0;
	int min_value, max_value;
	memset( arr, 0, sizeof( int ) * MAX_SIZE );

	len += 1;
	min_max_insert( arr, len, 7 );
	len += 1;
	min_max_insert( arr, len, 70 );
	len += 1;
	min_max_insert( arr, len, 40 );
	len += 1;
	min_max_insert( arr, len, 30 );
	len += 1;
	min_max_insert( arr, len, 9 );
	len += 1;
	min_max_insert( arr, len, 10 );
	len += 1;
	min_max_insert( arr, len, 15 );
	len += 1;
	min_max_insert( arr, len, 45 );
	len += 1;
	min_max_insert( arr, len, 50 );
	len += 1;
	min_max_insert( arr, len, 30 );
	len += 1;
	min_max_insert( arr, len, 20 );
	len += 1;
	min_max_insert( arr, len, 12 );
	len += 1;
	min_max_insert( arr, len, 5 );

	for ( i = 1; i <= len; i++ ){
		printf("%d ", arr[ i ] );
		if ( 0 == ( i + 1 ) % 5 ){
			printf("\n");
		}
	}

	min_value = delete_min( arr, len );
	printf("\nthe min value is:%d\n", min_value );
	len -= 1;
	for ( i = 1; i <= len; i++ ){
		printf("%d ", arr[ i ] );
		if ( 0 == ( i + 1 ) % 5 ){
			printf("\n");
		}
	}

	max_value = delete_max( arr, len );
	printf("\nthe max value is:%d\n", max_value );
	len -= 1;
	for ( i = 1; i <= len; i++ ){
		printf("%d ", arr[ i ] );
		if ( 0 == ( i + 1 ) % 5 ){
			printf("\n");
		}
	}

	printf("\n");

	return 0;
}

void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}

void min_max_insert( int heap[], int len, int item )
{
	int parent;
	if ( MAX_SIZE == len ){
		fprintf( stderr, "the heap is full\n" );
		return;
	}

	parent = len / 2;
	if ( !parent ){
		heap[ 1 ] = item;
	}
	else{
		switch( level( parent ) ){
			case 0:
				if ( item < heap[ parent ] ){
					heap[ len ] = heap[ parent ];
					verify_min( heap, parent, item );
				}
				else{
					verify_max( heap, len, item );
				}
				break;
			case 1:
				if ( item > heap[ parent ] ){
					heap[ len ] = heap[ parent ];
					verify_max( heap, parent, item );
				}
				else{
					verify_min( heap, len, item );
				}
		}
	}
}

int level( int parent )
{
	return (int)( log( parent ) / log( 2 ) ) % 2;
}

void verify_max( int heap[], int i, int item )
{
	int grandparent = i / 4;
	while ( grandparent ){
		if ( item > heap[ grandparent ] ){
			heap[ i ] = heap[ grandparent ];
			i = grandparent;
			grandparent /= 4;
		}
		else{
			break;
		}
	}
	heap[ i ] = item;
}

void verify_min( int heap[], int i, int item )
{
	int grandparent = i / 4;
	while ( grandparent ){
		if ( item < heap[ grandparent ] ){
			heap[ i ] = heap[ grandparent ];
			i = grandparent;
			grandparent /= 4;
		}
		else{
			break;
		}
	}

	heap[ i ] = item;
}

int delete_min( int heap[], int len )
{
	int i, last, k, parent;
	int x;
	if ( !len ){
		fprintf( stderr, "the heap is empty\n" );
		return INT_MAX;
	}
	heap[ 0 ] = heap[ 1 ];
	x = heap[ len-- ];
	for ( i = 1, last = len / 2; i <= last; ){
		k = min_child_grandchild( heap, i, len );
		/*新的根节点为最小结点*/
		if ( x <= heap[ k ] ){
			break;
		}
		heap[ i ] = heap[ k ];
		if ( k <= 2 * i + 1 ){
			i = k;
			break;
		}
		parent = k / 2;
		if ( x > heap[ parent ] ){
			swap( &heap[ parent ], &x );
		}
		i = k;
	}
	heap[ i ] = x;
	return heap[ 0 ];
}

int min_child_grandchild( int arr[], int parent, int len )
{
	int min_value = INT_MAX;
	int i = 2 * parent;
	int min_index = 0;
	for ( ; i <= len; i++ ){
		if ( arr[ i ] < min_value ){
			min_value = arr[ i ];
			min_index = i;
		}
	}

	return min_index;
}

int delete_max( int arr[], int len )
{
	int max_index = 0;
	int i, x, last, k, parent;
	if ( !len ){
		fprintf( stderr, "the heap is empty\n" );
		return INT_MAX;
	}
	if ( arr[ 2 ] > arr[ 3 ] ){
		arr[ 0 ] = arr[ 2 ];
		max_index = 2;
	}
	else{
		arr[ 0 ] = arr[ 3 ];
		max_index = 3;
	}
	x = arr[ len-- ];
	for ( i = max_index, last = len / 2; i <= last ; ){
		k = max_child_grandchild( arr, i, len );
		if ( x >= arr[ k ] ){
			break;
		}
		arr[ i ] = arr[ k ];
		if ( k <= 2 * i + 1 ){
			i = k;
			break;
		}
		parent = k / 2;
		if ( x < arr[ parent ] ){
			swap( &arr[ parent ], &x );
		}
		i = k;
	}

	arr[ i ] = x;
	return arr[ 0 ];
}

int max_child_grandchild( int arr[], int parent, int len )
{
	int max_value = INT_MIN;
	int i = 2 * parent;
	int max_index = 0;
	for ( ; i <= len; i++ ){
		if ( arr[ i ] > max_value ){
			max_value = arr[ i ];
			max_index = i;
		}
	}

	return max_index;
}



程序输出:

具体请参考<数据结构(C语言版)>上面的内容.


9.2 双端堆

定义:双端堆是一颗完全二叉树,该完全二叉树要么为空,要么同时满足下列性质:

  1. 根结点不包含元素.

  2. 左子树是一个最小堆

  3. 右子树是一个最大堆

  4. 如果右子树不为空,则令i是左子树中任意一个结点,j是i在右子树中的对应结点.如果i在右子树中的对应结点j不存在,则令j为i的父结点在右子树中的对应结点.对于结点i和j,结点i的关键字值小于等于结点j的关键字值.

第一段程序:插入结点:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAX_SIZE 100

/*双端堆的插入操作*/
void deap_insert( int deap[], int len, int x );
/*若n位于双端堆中的最大堆,则返回1,否则返回0*/
int max_heap( int n );
/*计算最小堆结点n的父节点对应的最大堆结点.*/
int max_partner( int n );
/*计算最大堆结点n对应的最小堆结点*/
int min_partner( int n );
/*将值x插入最小堆指定的位置*/
void min_insert( int deap[], int index, int x );
/*将值x插入最大堆指定的位置*/
void max_insert( int deap[], int index, int x );
/*交换两个数*/
void swap( int *px, int *py );

int main( void )
{
	int len = 1;
	int i = 0;
	int deap[ MAX_SIZE ];
	memset( deap, 0, sizeof( int ) * MAX_SIZE );

	len += 1;
	deap_insert( deap, len, 5 );
	len += 1;
	deap_insert( deap, len, 45 );
	len += 1;
	deap_insert( deap, len, 10 );
	len += 1;
	deap_insert( deap, len, 8 );
	len += 1;
	deap_insert( deap, len, 25 );
	len += 1;
	deap_insert( deap, len, 40 );
	len += 1;
	deap_insert( deap, len, 15 );
	len += 1;
	deap_insert( deap, len, 19 );
	len += 1;
	deap_insert( deap, len, 9 );
	len += 1;
	deap_insert( deap, len, 30 );
	len += 1;
	deap_insert( deap, len, 20 );
	len += 1;
	deap_insert( deap, len, 4 );
	
	for ( i = 2; i <= len; i++ ){
		printf("%d ", deap[ i ] );
		if ( 0 == ( i % 6 ) ){
			printf("\n");
		}
	}

	return 0;
}

void deap_insert( int deap[], int len, int x )
{
	int i;
	if ( MAX_SIZE == len ){
		fprintf(stderr, "the heap is full\n");
		return;
	}

	if ( 2 == len ){
		deap[ 2 ] = x;
	}
	else switch( max_heap( len ) ){
		case 0:
			i = max_partner( len );
			if ( x > deap[ i ] ){
				deap[ len ] = deap[ i ];
				max_insert( deap, i, x );
			}
			else{
				min_insert( deap, len, x );
			}
			break;
		case 1:
			i = min_partner( len );
			if ( x < deap[ i ] ){
				deap[ len ] = deap[ i ];
				min_insert( deap, i, x );
			}
			else{
				max_insert( deap, len, x );
			}
	}
}

/*头结点为空结点,并且索引为1.判断索引n是位于最小堆还是最大堆*/
int max_heap( int n )
{
	int exp = ( int )( log( n ) / log( 2 ) );
	if ( ( pow( 2.0, exp ) <= n ) && ( n < pow( 2.0, exp ) + pow( 2.0, exp - 1 ) ) ){
		return 0;
	}

	return 1;
}

/*计算最小堆结点n的父节点对应的最大堆结点.*/
int max_partner( int n )
{
	return ( int )( ( n + pow( 2.0, ( int )( log( n ) / log( 2 ) ) - 1 ) ) / 2 );
}

/*计算最大堆结点n对应的最小堆结点*/
int min_partner( int n )
{
	return n - ( int )( pow( 2.0, ( int )( log( n ) / log( 2 ) ) - 1 ) );
}

/*将值x插入最小堆指定的位置*/
void min_insert( int deap[], int index, int x )
{
	int parent = index / 2;
	deap[ index ] = x;
	if ( 1 == parent ){
		deap[ index ] = x;
	}
	else{
		while ( parent > 1 ){
			if ( deap[ index ] < deap[ parent ] ){
				swap( &deap[ index ], &deap[ parent ] );
			}
			index /= 2;
			parent = index / 2;
		}
	}
}

/*将值x插入最大堆指定的位置*/
void max_insert( int deap[], int index, int x )
{
	int parent = index / 2;
	deap[ index ] = x;
	if ( 1 == parent ){
		deap[ index ] = x;
	}
	else{
		while ( parent > 1 ){
			if ( deap[ index ] > deap[ parent ] ){
				swap( &deap[ index ], &deap[ parent ] ); 
			}
			index /= 2;
			parent = index / 2;
		}
	}
}

/*交换两个数*/
void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}

程序输出:

根据书上一步步写出来.刚开始学习C语言的时候就应该这样,不急不躁.先学会如何编程,然后再想如何编好程序.

双端堆的作用就是方便删除最小最大值.代码如下:

备注:在删除最小元素或者最大元素的时候,存在一个非常隐蔽的BUG是:假设我要在最大堆中插入20,而在最小堆中对应的结点是9,那么符合性质4.但是结点9的孩子一个是30,一个是40怎么办?他们的孩子结点大于20,不符合性质4,这时候就需要进行特殊的处理.代码如下:

/*删除最小元素,这里len是已经删除掉元素后的长度*/
int deap_delete_min( int deap[], int len )
{
	int temp, i, j, k;
	if ( len < 2 ){
		fprintf(stderr, "the deap is empty\n");
		return INT_MAX;
	}
	deap[ 0 ] = deap[ 2 ];
	temp = deap[ len + 1 ];
	for ( i = 2; i * 2 <= len; ){
		j = i * 2;
		if ( j + 1 <= len ){
			if ( deap[ j ] > deap[ j + 1 ] ){
				j++;
			}
		}
		deap[ i ] = deap[ j ];
		i = j;
	}
	deap[ i ] = temp;
	k = max_partner( i );
	/*判断最小堆的孩子结点小于最大堆要插入的结点*/
	while ( k <= len ){
		if ( deap[ i ] > deap[ k ] ){
			deap[ i ] = deap[ k ];
			max_insert( deap, k, temp );
			break;
		}
		k *= 2;
		if ( k + 1 <= len ){
			if ( deap[ k ] > deap[ k + 1 ] ){
				k += 1;
			}
		}
	}
	
	return deap[ 0 ];
}

/*删除最大元素*/
int deap_delete_max( int deap[], int len )
{
	int temp, i, j, k;
	if ( len < 3 ){
		fprintf(stderr, "the deap is empty\n");
		return INT_MAX;
	}
	deap[ 0 ] = deap[ 3 ];
	temp = deap[ len + 1 ];
	for ( i = 3; i * 2 <= len; ){
		j = i * 2;
		if ( j + 1 <= len ){
			if ( deap[ j ] < deap[ j + 1 ] ){
				j++;
			}
		}
		deap[ i ] = deap[ j ];
		i = j;
	}

	deap[ i ] = temp;
	k = min_partner( i );
	/*判断最大堆的孩子结点大于最小堆要插入的结点*/
	while ( k <= len ){
		if ( deap[ i ] < deap[ k ] ){
			deap[ i ] = deap[ k ];
			min_insert( deap, k, temp );
			break;
		}
		k *= 2; 
		if ( k + 1 <= len ){
			if ( deap[ k ] < deap[ k + 1 ] ){
				k += 1;
			}
		}
	}
	
	return deap[ 0 ];
}

所有的代码罗列如下:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

#define MAX_SIZE 100

/*双端堆的插入操作*/
void deap_insert( int deap[], int len, int x );
/*若n位于双端堆中的最大堆,则返回1,否则返回0*/
int max_heap( int n );
/*计算最小堆结点n的父节点对应的最大堆结点.*/
int max_partner( int n );
/*计算最大堆结点n对应的最小堆结点*/
int min_partner( int n );
/*将值x插入最小堆指定的位置*/
void min_insert( int deap[], int index, int x );
/*将值x插入最大堆指定的位置*/
void max_insert( int deap[], int index, int x );
/*交换两个数*/
void swap( int *px, int *py );
/*删除最小元素*/
int deap_delete_min( int deap[], int len );
/*删除最大元素*/
int deap_delete_max( int deap[], int len );

int main( void )
{
	int len = 1;
	int i = 0;
	int deap[ MAX_SIZE ];
	int minValue = 0;
	int maxValue = 0;
	memset( deap, 0, sizeof( int ) * MAX_SIZE );

	len += 1;
	deap_insert( deap, len, 5 );
	len += 1;
	deap_insert( deap, len, 45 );
	len += 1;
	deap_insert( deap, len, 10 );
	len += 1;
	deap_insert( deap, len, 8 );
	len += 1;
	deap_insert( deap, len, 25 );
	len += 1;
	deap_insert( deap, len, 40 );
	len += 1;
	deap_insert( deap, len, 15 );
	len += 1;
	deap_insert( deap, len, 19 );
	len += 1;
	deap_insert( deap, len, 9 );
	len += 1;
	deap_insert( deap, len, 30 );
	len += 1;
	deap_insert( deap, len, 20 );
	len += 1;
	deap_insert( deap, len, 4 );
	
	len -= 1;
	minValue = deap_delete_min( deap, len );
	len -= 1;
	maxValue = deap_delete_max( deap, len );

	printf("the min value is : %d\n", minValue );
	printf("the max value is : %d\n", maxValue );
	for ( i = 2; i <= len; i++ ){
		printf("%3d ", deap[ i ] );
		if ( 0 == ( i % 6 ) ){
			printf("\n");
		}
	}
	printf("\n");

	return 0;
}

void deap_insert( int deap[], int len, int x )
{
	int i;
	if ( MAX_SIZE == len ){
		fprintf(stderr, "the heap is full\n");
		return;
	}

	if ( 2 == len ){
		deap[ 2 ] = x;
	}
	else switch( max_heap( len ) ){
		case 0:
			i = max_partner( len );
			if ( x > deap[ i ] ){
				deap[ len ] = deap[ i ];
				max_insert( deap, i, x );
			}
			else{
				min_insert( deap, len, x );
			}
			break;
		case 1:
			i = min_partner( len );
			if ( x < deap[ i ] ){
				deap[ len ] = deap[ i ];
				min_insert( deap, i, x );
			}
			else{
				max_insert( deap, len, x );
			}
	}
}

/*头结点为空结点,并且索引为1.判断索引n是位于最小堆还是最大堆*/
int max_heap( int n )
{
	int exp = ( int )( log( n ) / log( 2 ) );
	if ( ( pow( 2.0, exp ) <= n ) && ( n < pow( 2.0, exp ) + pow( 2.0, exp - 1 ) ) ){
		return 0;
	}

	return 1;
}

/*计算最小堆结点n的父节点对应的最大堆结点.*/
int max_partner( int n )
{
	return ( int )( ( n + pow( 2.0, ( int )( log( n ) / log( 2 ) ) - 1 ) ) / 2 );
}

/*计算最大堆结点n对应的最小堆结点*/
int min_partner( int n )
{
	return n - ( int )( pow( 2.0, ( int )( log( n ) / log( 2 ) ) - 1 ) );
}

/*将值x插入最小堆指定的位置*/
void min_insert( int deap[], int index, int x )
{
	int parent = index / 2;
	deap[ index ] = x;
	if ( 1 == parent ){
		deap[ index ] = x;
	}
	else{
		while ( parent > 1 ){
			if ( deap[ index ] < deap[ parent ] ){
				swap( &deap[ index ], &deap[ parent ] );
			}
			index /= 2;
			parent = index / 2;
		}
	}
}

/*将值x插入最大堆指定的位置*/
void max_insert( int deap[], int index, int x )
{
	int parent = index / 2;
	deap[ index ] = x;
	if ( 1 == parent ){
		deap[ index ] = x;
	}
	else{
		while ( parent > 1 ){
			if ( deap[ index ] > deap[ parent ] ){
				swap( &deap[ index ], &deap[ parent ] ); 
			}
			index /= 2;
			parent = index / 2;
		}
	}
}

/*交换两个数*/
void swap( int *px, int *py )
{
	int temp = *px;
	*px = *py;
	*py = temp;
}

/*删除最小元素,这里len是已经删除掉元素后的长度*/
int deap_delete_min( int deap[], int len )
{
	int temp, i, j, k;
	if ( len < 2 ){
		fprintf(stderr, "the deap is empty\n");
		return INT_MAX;
	}
	deap[ 0 ] = deap[ 2 ];
	temp = deap[ len + 1 ];
	for ( i = 2; i * 2 <= len; ){
		j = i * 2;
		if ( j + 1 <= len ){
			if ( deap[ j ] > deap[ j + 1 ] ){
				j++;
			}
		}
		deap[ i ] = deap[ j ];
		i = j;
	}
	deap[ i ] = temp;
	k = max_partner( i );
	/*判断最小堆的孩子结点小于最大堆要插入的结点*/
	while ( k <= len ){
		if ( deap[ i ] > deap[ k ] ){
			deap[ i ] = deap[ k ];
			max_insert( deap, k, temp );
			break;
		}
		k *= 2;
		if ( k + 1 <= len ){
			if ( deap[ k ] > deap[ k + 1 ] ){
				k += 1;
			}
		}
	}
	
	return deap[ 0 ];
}

/*删除最大元素*/
int deap_delete_max( int deap[], int len )
{
	int temp, i, j, k;
	if ( len < 3 ){
		fprintf(stderr, "the deap is empty\n");
		return INT_MAX;
	}
	deap[ 0 ] = deap[ 3 ];
	temp = deap[ len + 1 ];
	for ( i = 3; i * 2 <= len; ){
		j = i * 2;
		if ( j + 1 <= len ){
			if ( deap[ j ] < deap[ j + 1 ] ){
				j++;
			}
		}
		deap[ i ] = deap[ j ];
		i = j;
	}

	deap[ i ] = temp;
	k = min_partner( i );
	/*判断最大堆的孩子结点大于最小堆要插入的结点*/
	while ( k <= len ){
		if ( deap[ i ] < deap[ k ] ){
			deap[ i ] = deap[ k ];
			min_insert( deap, k, temp );
			break;
		}
		k *= 2; 
		if ( k + 1 <= len ){
			if ( deap[ k ] < deap[ k + 1 ] ){
				k += 1;
			}
		}
	}
	
	return deap[ 0 ];
}

程序输出:


9.3 左高树

备注:在描述概念上书上有图展示,但是我不知道怎么画好一幅图(或者这样会造成臃肿),所以阐述概念的时候不会很清晰,请参考<数据结构(C语言版)>这本书.

左高树的一个应用是合并操作,应用场景是:当某个优先队列的服务器关闭时,就需要将其与另一个正在运行服务器的优先队列合并.如果两个队列的元素总数为n,则一般的堆结构的复杂度为n,但是左高树可以达到log(n).

左高树的简单定义就是:左子树比对应的右子树高.它的数据结构中会有一项shortest,表示其结点到叶子节点的长度.用于判断左子树高于右子树,即left.shortest >= right.shortest.

定义:最小(最大)左高树是一棵左高树,其中每个内部结点的关键字值都不大于(不小于)该结点儿子结点(如果有的话)的关键字值.换句话说,一棵最小(最大)左高树既是一棵左高树,同时又是一棵最小(最大)树.

程序用层序遍历输出.但是一个层序遍历无法推测出一棵树的原本模样,所以我们提供了中序和前序输出用于比较:

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

/*宏定义类似于C++的模板技术,可以不考虑交换的数据类型*/
#define SWAP( x, y, t ) ( (t) = (x),(x) = (y), (y) = (t) )
#define MAX_SIZE 100

typedef struct LEFTISTTREE{
	struct LEFTISTTREE		*leftChild;
	struct LEFTISTTREE		*rightChild;
	int								data;
	int								shortest;
} Leftisttree;

Leftisttree *stack[ MAX_SIZE ];
int top = 0;
int rear = 0;

/*合并两棵左高树*/
void min_combine( Leftisttree **a, Leftisttree **b );
/*合并两棵最小左高树*/
void min_union( Leftisttree **a, Leftisttree **b );
/*初始化一个左高树结点*/
void init_node( Leftisttree **b, int data );
/*打印一棵左高树:层序输出*/
void show_tree( Leftisttree *a );
/*打印一棵左高树:中序输出*/
void show_mid_tree( Leftisttree *a );
void show_pre_tree( Leftisttree *a );

int main( void )
{
	Leftisttree *a = NULL;
	Leftisttree *b = NULL;
	Leftisttree *c = NULL;
	
	init_node( &b, 2 );
	min_combine( &a, &b );
	init_node( &b, 7 );
	min_combine( &a, &b );
	init_node( &b, 50 );
	min_combine( &a, &b );
	init_node( &b, 11 );
	min_combine( &a, &b );
	init_node( &b, 80 );
	min_combine( &a, &b );
	init_node( &b, 13 );
	min_combine( &a, &b );

	printf("tree a is:\n");
	show_tree( a );
	printf("->NULL\n");

	init_node( &b, 5 );
	min_combine( &c, &b );
	init_node( &b, 9 );
	min_combine( &c, &b );
	init_node( &b, 8 );
	min_combine( &c, &b );
	init_node( &b, 12 );
	min_combine( &c, &b );
	init_node( &b, 10 );
	min_combine( &c, &b );
	init_node( &b, 20 );
	min_combine( &c, &b );
	init_node( &b, 18 );
	min_combine( &c, &b );
	init_node( &b, 15 );
	min_combine( &c, &b );

	printf("\ntree c is:\n");
	show_tree( c );
	printf("->NULL\n");

	min_combine( &a, &c );

	printf("\nnew tree a is:\n");
	show_tree( a );
	printf("->NULL\n");
	show_mid_tree( a );
	printf("->NULL\n");
	show_pre_tree( a );
	printf("->NULL\n");

	return 0;
}

void init_node( Leftisttree **b, int data )
{
	if ( !*b ){
		*b = ( Leftisttree *)malloc( sizeof( Leftisttree ) );
	}
	( *b )->data = data;
	( *b )->leftChild = ( *b )->rightChild = NULL;
	( *b )->shortest = 1;
}

void show_tree( Leftisttree *tree )
{
	top = 0;
	rear = 0;
	stack[ rear++ ] = tree;
	while ( 1 ){
		tree = stack[ top++ ];
		if ( tree ){
			printf("%d->", tree->data );
			if ( tree->leftChild ){
				stack[ rear++ ] = tree->leftChild;
			}
			if ( tree->rightChild ){
				stack[ rear++ ] = tree->rightChild;
			}
		}
		else{
			break;
		}
	}
}

void show_mid_tree( Leftisttree *a )
{
	if ( a ){
		printf("%d->", a->data );
		show_mid_tree( a->leftChild );
		show_mid_tree( a->rightChild );
	}
}

void show_pre_tree( Leftisttree *a )
{
	if ( a ){
		show_pre_tree( a->leftChild );
		printf("%d->", a->data );
		show_pre_tree( a->rightChild );
	}
}

void min_combine( Leftisttree **a, Leftisttree **b )
{
	if ( !*a ){
		*a = *b;
	}
	else if ( *b ){
		min_union( a, b );
	}
	*b = NULL;
}

void min_union( Leftisttree **a, Leftisttree **b )
{
	Leftisttree *temp;
	if ( ( *a )->data > ( *b )->data ){
		SWAP( *a, *b, temp );
	}
	if ( !( *a )->rightChild ){
		( *a )->rightChild = *b;
	}
	else{
		min_union( &( *a )->rightChild, b );
	}

	if ( !( *a )->leftChild ){
		( *a )->leftChild = ( *a )->rightChild;
		( *a )->rightChild = NULL;
	}
	else if ( ( *a )->leftChild->shortest < ( *a )->rightChild->shortest ){
		SWAP( ( *a )->leftChild, ( *a )->rightChild, temp );
	}
	( *a )->shortest = ( !( *a )->rightChild ) ? 1 : ( *a )->rightChild->shortest + 1;
}

程序输出:

PS:如果你想删除最小元素,则让最小元素(根节点)的左子树和右子树合并即可.而且这里用到的是指针的指针,可以保证正确的修改.还记得吗?C语言只支持传值的.


关于二项堆和菲波那契堆,书上只有简单描述,没有具体的代码,故略过.等看<数据结构和算法分析(C语言描述)>或者<算法导论>时候深入了解.



© 著作权归作者所有

共有 人打赏支持
fzyz_sb
粉丝 404
博文 209
码字总数 447144
作品 0
武汉
程序员
做游戏,学编程(C语言) 网易云课堂MOOC视频

应一些同学的要求,把这学期上C语言编程课的讲课视频录制剪辑,上传到网易云课堂,感兴趣的朋友可以在线观看,欢迎多提宝贵意见。 MOOC视频链接:http://study.163.com/course/introduction....

童晶 ⋅ 2017/11/07 ⋅ 0

微软面试、经典算法、编程艺术、红黑树4大系列总结

无私分享,造福天下 以下是本blog内的微软面试100题系列,经典算法研究系列,程序员编程艺术系列,红黑树系列4大经典原创系列作品与一些重要文章的集锦。 一、微软面试100题系列 横空出世,席...

长平狐 ⋅ 2013/01/06 ⋅ 0

Linux C编程如何使用联机帮助来解决编程问题?

1.背景 多次学习C语言一直无法踏入C语言的大门,每次都是在学习C语言中的那些系统调用库函数等望而却只,linux下的系统调用需要我们去记忆一些没有规律的结构体和一些大写的宏定义并且还有一...

Jeff_Linux ⋅ 2014/07/06 ⋅ 0

《程序员面试宝典》精华 编程语言部分

《程序员面试宝典》精华 编程语言部分 正所谓取其精华,去其糟粕。本文谨记录下《程序员面试宝典》一些关键的知识点、易错点,对于一些虽然重要但书中没有解释清楚的地方不做记录。当然这里的...

modernizr ⋅ 2014/08/11 ⋅ 2

考研-专业课-c语言

为了我家娘子,猪猪臭 本人计划考研:报考学校北京工业大学--计算机 专业课编号985:教材为C语言程序设计案例教程和严蔚敏的数据结构那本 我知道 本书是没有答案的 下面的全都是 自己写的 并在...

20111564 ⋅ 2014/10/16 ⋅ 0

《Linux设备驱动开发详解(第2版)》视频

http://edu.51cto.com/course/course_id-379-page-1.html http://edu.51cto.com/course/course_id-379-page-2.html 课时目录共13课时...

21cnbao ⋅ 2013/07/09 ⋅ 0

业余爱好者的C程序设计学习之路

我学习和工作的方向都是化工,和 IT 专业一点边都不搭,属于程序设计爱好者一类。坚持了很多年了,谈谈我的认识。 一、为什么是C 汇编太难,直接下手会吓死宝宝的。 basic 不能考虑,因为“对...

四彩 ⋅ 2016/02/04 ⋅ 2

数据结构算法书籍推荐

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

modernizr ⋅ 2014/05/22 ⋅ 13

书籍推荐:《实战Java虚拟机——JVM故障诊断与性能优化》下载

本书详细介绍Java虚拟机的基本原理和优化诊断方法。其中重点介绍Java虚拟机的体系结构、常用的虚拟机参数、Java虚拟机的垃圾回收原理、算法以及目前虚拟机所支持的各种垃圾回收器及其区别、特...

ddddd8 ⋅ 2017/11/29 ⋅ 0

200 行 Java 代码搞定计算器程序

原文出处:CarpenterLee 发现了大学时候写的计算器小程序,还有个图形界面,能够图形化展示表达式语法树,哈哈;) 只有200行Java代码,不但能够计算加减乘除,还能够匹配小括号~ 代码点评: ...

CarpenterLee ⋅ 01/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 29分钟前 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 39分钟前 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 56分钟前 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

table eg

user_id user_name full_name 1 zhangsan 张三 2 lisi 李四 `` ™ [========] 2018-06-18 09:42:06 星期一½ gdsgagagagdsgasgagadsgdasgagsa...

qwfys ⋅ 今天 ⋅ 0

一个有趣的Java问题

先来看看源码: public class TestDemo { public static void main(String[] args) { Integer a = 10; Integer b = 20; swap(a, b); System.out......

linxyz ⋅ 今天 ⋅ 0

十五周二次课

十五周二次课 17.1mysql主从介绍 17.2准备工作 17.3配置主 17.4配置从 17.5测试主从同步 17.1mysql主从介绍 MySQL主从介绍 MySQL主从又叫做Replication、AB复制。简单讲就是A和B两台机器做主...

河图再现 ⋅ 今天 ⋅ 0

docker安装snmp rrdtool环境

以Ubuntu16:04作为基础版本 docker pull ubuntu:16.04 启动一个容器 docker run -d -i -t --name flow_mete ubuntu:16.04 bash 进入容器 docker exec -it flow_mete bash cd ~ 安装基本软件 ......

messud4312 ⋅ 今天 ⋅ 0

OSChina 周一乱弹 —— 快别开心了,你还没有女友呢。

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @莱布妮子 :分享吴彤的单曲《好春光》 《好春光》- 吴彤 手机党少年们想听歌,请使劲儿戳(这里) @clouddyy :小萝莉街上乱跑,误把我认错成...

小小编辑 ⋅ 今天 ⋅ 9

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部