数据结构(C语言版)第九章:堆结构
博客专区 > fzyz_sb 的博客 > 博客详情
数据结构(C语言版)第九章:堆结构
fzyz_sb 发表于4年前
数据结构(C语言版)第九章:堆结构
  • 发表于 4年前
  • 阅读 272
  • 收藏 9
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

摘要: 各种复杂的堆结构

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语言描述)>或者<算法导论>时候深入了解.



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