(八)数据结构之最大堆的简单实现

ゞ浴缸里的玫瑰 2022-06-08 06:26 186阅读 0赞

## 1、什么是堆？ ##

堆是一种优先队列。特殊的队列，取出元素的顺序是按照元素的优先权（关键字）大小，而不是元素进入队列的先后顺序。

堆的两个特性：  
a、结构性  
用数组表示的完全二叉树  
b、有序性  
任一结点的关键字是其子树所有结点的最大值（或最小值）

## 2、最大堆的实现 ##

### 2.1 基本数据结构 ###

/* 定义最大元素的界限 */
    #define MAXDATA		10000
    
    /* 创建基本的数据结构 */
    typedef int ElementType;
    typedef struct HeapStruct *MaxHeap;
    struct HeapStruct {
    	ElementType *Elements; 	/* 存储堆元素的数组 */
    	int Size; 				/* 堆的当前元素个数 */
    	int Capacity; 			/* 堆的最大容量 */
    };

### 2.2 创建一个空堆 ###

/* 创建一个容量为Capacity的最大堆 */
    MaxHeap Create( int Capacity )
    { 
    	MaxHeap H = (MaxHeap)malloc( sizeof( struct HeapStruct ) );
    	H->Elements = (ElementType *)malloc( (Capacity+1) * sizeof(ElementType));
    	H->Size = 0;
    	H->Capacity = Capacity;
    	H->Elements[0] = MAXDATA;	/* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */
    
    	return H;
    }

### 2.3 插入操作 ###

/* 向最大堆中插入一个元素 */
    void Insert( MaxHeap H, ElementType item )
    { 
    	/* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */
    	int i;
    	
    	if ( IsFull(H) ) 
    	{
    		printf("The heap is full!\n");
    		return;
    	}
    
    	/* i指向插入后堆中的最后一个元素的位置 */
    	i = ++H->Size; 		
    	for ( ; H->Elements[i/2] < item; i/=2 )
    	{
    		H->Elements[i] = H->Elements[i/2];
    	}
    	H->Elements[i] = item; 
    }

### 2.4 删除操作 ###

/* 删除堆中最大的一个元素，并删除一个结点 */
    ElementType DeleteMax( MaxHeap H )
    { 
    	int Parent, Child;
    	ElementType MaxItem, temp;
    	
    	if ( IsEmpty(H) ) 
    	{
    		printf("The heap is empty!\n");
    		return -1;
    	}
    	
    	MaxItem = H->Elements[1]; 
    	temp = H->Elements[H->Size--];
    	
    	for( Parent=1; Parent*2<=H->Size; Parent=Child ) 
    	{
    		Child = Parent * 2;
    		if( (Child!= H->Size) && (H->Elements[Child] < H->Elements[Child+1]) )
    			Child++; 		/* Child指向左右子结点的较大者 */
    		if( temp >= H->Elements[Child] ) 
    			break;
    		else 
    			H->Elements[Parent] = H->Elements[Child];
    	}
    	H->Elements[Parent] = temp;
    	
    	return MaxItem;
    }

### 2.5 完整示例代码实现 ###

/* 最大堆的基本操作 */
    #include <stdio.h>
    #include <stdlib.h>
    
    /* 定义最大元素的界限 */
    #define MAXDATA		10000
    
    /* 创建基本的数据结构 */
    typedef int ElementType;
    typedef struct HeapStruct *MaxHeap;
    struct HeapStruct {
    	ElementType *Elements; 	/* 存储堆元素的数组 */
    	int Size; 				/* 堆的当前元素个数 */
    	int Capacity; 			/* 堆的最大容量 */
    };
    
    /* 创建一个容量为Capacity的最大堆 */
    MaxHeap Create( int Capacity )
    { 
    	MaxHeap H = (MaxHeap)malloc( sizeof( struct HeapStruct ) );
    	H->Elements = (ElementType *)malloc( (Capacity+1) * sizeof(ElementType));
    	H->Size = 0;
    	H->Capacity = Capacity;
    	H->Elements[0] = MAXDATA;	/* 定义“哨兵”为大于堆中所有可能元素的值，便于以后更快操作 */
    
    	return H;
    }
    
    /* 销毁一个最大堆的结构 */
    void Destroy(MaxHeap H)
    {
    	if(H != NULL)
    	{
    		if(H->Elements != NULL)
    		{
    			free(H->Elements);
    			H->Elements = NULL;
    		}
    		free(H);
    		H = NULL;
    	}
    }
    
    /* 定义一个函数，判断最大堆是否为满，为满返回1，否则返回0 */
    int IsFull(MaxHeap H)
    {
    	return (H->Size == H->Capacity);
    }
    
    /* 向最大堆中插入一个元素 */
    void Insert( MaxHeap H, ElementType item )
    { 
    	/* 将元素item 插入最大堆H，其中H->Elements[0]已经定义为哨兵 */
    	int i;
    	
    	if ( IsFull(H) ) 
    	{
    		printf("The heap is full!\n");
    		return;
    	}
    
    	/* i指向插入后堆中的最后一个元素的位置 */
    	i = ++H->Size; 		
    	for ( ; H->Elements[i/2] < item; i/=2 )
    	{
    		H->Elements[i] = H->Elements[i/2];
    	}
    	H->Elements[i] = item; 
    }
    
    /* 判断这个堆栈是否为空，为空返回1，否则返回0 */
    int IsEmpty(MaxHeap H)
    {
    	return (H->Size == 0);
    }
    
    /* 删除堆中最大的一个元素，并删除一个结点 */
    ElementType DeleteMax( MaxHeap H )
    { 
    	int Parent, Child;
    	ElementType MaxItem, temp;
    	
    	if ( IsEmpty(H) ) 
    	{
    		printf("The heap is empty!\n");
    		return -1;
    	}
    	
    	MaxItem = H->Elements[1]; 
    	temp = H->Elements[H->Size--];
    	
    	for( Parent=1; Parent*2<=H->Size; Parent=Child ) 
    	{
    		Child = Parent * 2;
    		if( (Child!= H->Size) && (H->Elements[Child] < H->Elements[Child+1]) )
    			Child++; 		/* Child指向左右子结点的较大者 */
    		if( temp >= H->Elements[Child] ) 
    			break;
    		else 
    			H->Elements[Parent] = H->Elements[Child];
    	}
    	H->Elements[Parent] = temp;
    	
    	return MaxItem;
    }
    
    /* 遍历这个堆中的所有元素 */
    void Traversal(MaxHeap H)
    {
    	int i;
    	if((H != NULL) && !IsEmpty(H))
    	{
    		for(i = 1; i <= H->Size; i++)
    			printf("%d ", H->Elements[i]);
    		printf("\n");
    	}
    }
    
    
    /* 程序入口 */
    int main()
    {
    	int i = 0;
    	ElementType temp;
    	MaxHeap heap = NULL;
    
    	/* 创建一个最大堆的结构指针 */
    	heap = Create(20);
    
    	/* 向这个最大堆中插入10个元素 */
    	printf("Input 10 numbers : ");
    	for(i = 0; i < 10; i++)
    	{
    		scanf("%d", &temp);
    		Insert(heap, temp);
    	}
    
    	/* 把里面的元素按照数组的先后顺序打印出来 */
    	printf("*********************************Traversal***********************************\n");
    	Traversal(heap);
    
    	/* 删除最大堆中的元素 */
    	printf("*********************************Delete twice********************************\n");
    	for(i = 0; i < 2; i++)
    	{
    		temp = DeleteMax(heap);
    		printf("%d ", temp);
    	}
    	printf("\n");
    
    	/* 把里面的元素按照数组的先后顺序打印出来 */
    	printf("*********************************Traversal***********************************\n");
    	Traversal(heap);
    
    	Destroy(heap);	/* 销毁一颗二叉树 */
    	return 0;
    }