数据结构---堆

文章目录

一、堆的两个特性

二、区分最大堆和最小堆

三、堆的抽象数据类型描述

这里举例用最大堆，最小堆同理

四、最大堆的建立

五、最大堆的插入

六、最大堆的删除

七、最大堆的打印

一、堆的两个特性

• 结构性：用数组表示的完全二叉树
• 有序性：任一结点的关键字是其子树所有结点的最大值或最小值

二、区分最大堆和最小堆

• 最大堆：最大值（MaxHeap）
• 最小堆：最小值（MinHeap）
  

三、堆的抽象数据类型描述：

四、最大堆的建立：

方法一：

#include <stdio.h>
#include <stdlib.h>
#define MinData -10001
#define MaxData 10001
typedef struct Heap *MinHeap;
typedef int ElementType;
struct Heap{
   
    ElementType *Elements;
    int Size;    //记录当前堆元素个数
    int Capacity;   //堆的最大容量
};
MaxHeap Create(int MaxSize)
{
   
    MinHeap H = (MinHeap)malloc(sizeof(struct Heap));
    H->Elements = (ElementType *)malloc((MaxSize+1)*sizeof(ElementType));
    H->Size = 0;
    H->Capacity = MaxSize;
    //定义下标为0的位置为“哨兵”，其数值小于小頂堆的最小值
    H->Elements[0] = MaxData;
    return H;
}

方法二：

#include<iostream>
using namespace std;
#define MAXN 1001
#define MINH -10001
#define MIN 10001
int H[MAXN],size;
void Create()
{
   
	size = 0;
	H[0] = MINH; //设置岗哨 
}

五、最大堆的插入

方法一：

void Insert(MinHeap H,ElementType X)
{
   
    int i;
    if(IsFull(H)){
   
    	printf("堆已满");
    	return ;
	}
    i = ++H->Size;//先++ 0下标存放哨兵
    for(;X>H->Elements[i/2];i/=2)
    H->Elements[i] = H->Elements[i/2];
    H->Elements[i] = X;   
    
}

方法二：

void Insert(int x)
{
   
	//将x插入h 建立最小堆 
	//i*2表示左儿子 i*2+1表示右儿子 
	//H[i/2]>x表示每次插入与父节点比较 
	//若小于父节点，则让父节点与插入结点互换 
	int i;
	//若要换成最大堆的话只需要将岗哨改为最大，并将H[i/2] > x改为H[i/2] < x
	for(i = ++size; x>H[i/2]; i/=2) 
		H[i] = H[i/2];
		H[i] = x;
 } 

六、最大堆的删除

方法一：

int DeleteMax(MinHeap H)
{
   
	//从最大堆H中取出键值最大的元素，并删除一个结点 
	int Parent,Child;
	int MaxItem,temp;
	if(IsEmpty(H))
	{
   
		printf("最大堆空");
		return ;
	}
	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//移动temp元素到下一层 
		H->Elements[Parent]=H->Elements[Child];
	}
	H->Elements[Parent]=temp;
	return MaxItem;
}

七、最大堆的打印

void PrintRoad(MinHeap H,int k)
{
   
	printf("%d",H->Elements[k]);
    while(k>1)
    {
   
        k/=2;
        printf(" %d",H->Elements[k]);
    }
    puts("");
}

	for(int i = 0; i < m; i++){
   
		cin>>temp;
		cout<<H[temp];
		while(temp>1){
   
			temp /= 2;
			cout<<" "<<H[temp];
		}
		cout<<endl;
	}