数据结构（九）堆

小咪咪 2022-04-22 10:15 70阅读 0赞

## 堆 ##

### 1. 什么是堆 ###

优先队列（priority Queue）：特殊的"队列"，取出元素的顺序是依照元素的优先级（关键字）大小，而不是元素进入队列的先后顺序，以**完全二叉树**存储

![20181104104440648.jpg][]

两个特性

*  结构性：用**数组**表示的**完全二叉树**
 *  有序性：任一结点的关键字是其子树所有结点的最大值（或最小值）
    
     *  “最大堆(MaxHeap)”，也称"大顶堆"：最大值
        
        ![20181104104459868.jpg][]
     *  “最小堆(MinHeap)”，也称"小顶堆"：最小值
        
        ![20181104104516209.jpg][]

![20181104104530440.jpg][]

### 2. 堆的抽象数据类型描述 ###

*  数据名称：最大堆（MaxHeap）
 *  数据对象集：完全二叉树，每个结点的元素值**不小于**其子结点的元素值
 *  操作集：最大堆 H ∈ MaxHeap，元素 item ∈ ElementType
    
    主要操作有：
    
     *  `MaxHeap Create(int MaxSize)`：创建一个空的最大堆
     *  `Boolean IsFull(MaxHeap H)`：判断最大堆 H 是否已满
     *  `Boolean Insert(MaxHeap H,ElementType item)`：将元素 item 插入最大堆 H
     *  `Boolean IsEmpty(MaxHeap H)`：判断最大堆 H 是否为空
     *  `ElementType DeleteMax(MaxHeap H)`：返回 H 中最大元素（高优先级）

#### 1. 插入 ####

插入数组最后一个位置，再从下往上找合适地方

#### 2. 删除 ####

删除根结点，将数组最后一个位置的数取到根结点，从上往下找合适地方

#include<stdio.h>
    #include<malloc.h>
    #define MaxData 100000
    #define ERROR -1
    typedef int ElementType;
    typedef struct HeapStruct *MaxHeap;
    struct HeapStruct{
        
    	ElementType *Elements;   // 存储堆元素的数组 
    	int Size;      // 堆的当前元素个数 
    	int Capacity;  // 堆的最大容量 
    };
    
    MaxHeap Create(int MaxSize);  // 建堆 
    bool IsFull(MaxHeap H);    // 判断堆是否满
    bool Insert(MaxHeap H,ElementType item);   // 插入元素
    bool IsEmpty(MaxHeap H);    //  判断堆是否为空
    ElementType DeleteMax(MaxHeap H);  // 删除并返回堆中最大元素
    void LevelOrderTraversal(MaxHeap H);  // 层序遍历 
    
    // 建堆 
    MaxHeap Create(int MaxSize){
        
    	MaxHeap H = (MaxHeap)malloc(sizeof(struct HeapStruct));
    	// Elements[0] 作为哨兵，堆元素从  Elements[1] 开始存放 
    	H->Elements = (ElementType *)malloc((MaxSize+1) * sizeof(ElementType));
    	H->Size = 0;
    	H->Capacity = MaxSize;
    	// "哨兵"大于堆中所有可能的值 
    	H->Elements[0] = MaxData;
    	return H;
    } 
    
    // 插入，从完全二叉树的最后一个位置插入 
    bool Insert(MaxHeap H,ElementType item){
        
    	if(IsFull(H)){
        
    		printf("堆已满，无法插入！\n");
    		return false;
    	}
    	int i = ++H->Size;  // 指向堆中最后一个位置 
    	for(;H->Elements[i/2] < item;i/=2)    // 向上找比 item 大的结点 
    		H->Elements[i] = H->Elements[i/2];  //  向下赋值 
    	H->Elements[i] = item;  // 找到了，把 item 值放进去 
    	return true;
    }
    
    // 删除，从根结点删除 
    ElementType DeleteMax(MaxHeap H){
        
    	int parent,child;
    	ElementType Max,tmp;
    	if(IsEmpty(H)){
        
    		printf("堆为空，无法删除！\n");
    		return ERROR;
    	}
    	Max = H->Elements[1];  // 拿到最大值
    	tmp = H->Elements[H->Size--];  // 拿到完全二叉树最后一个值 
    	// 判别条件：parent 是否有左孩子结点 
    	for(parent=1;parent*2<=H->Size;parent=child){
        
    		// 左右孩子结点中找较大的值 
    		child = 2 * parent;  // 左孩子结点 
    		// child!=H->Size 表示 child 不为当前最后一个结点，即 parent 有右孩子结点 
    		if((child!=H->Size) &&(H->Elements[child] < H->Elements[child+1]))
    			child++;  
    		// 给 tmp 找个合适的位置 
    		// 如果当前左右孩子结点比 tmp 都小，说明 tmp 位置已经合适 
    		if(H->Elements[child] <= tmp)
    			break;
    		else    // 否则把较大的孩子结点提上来，自己继续下去找 
    			H->Elements[parent] = H->Elements[child];
    	}
    	H->Elements[parent] = tmp;  // 在合适的位置把 tmp 放进去 
    	return Max;
    } 
    
    // 判断是否已经满 
    bool IsFull(MaxHeap H){
        
    	return (H->Size == H->Capacity);
    }
    
    // 判断是否为空
    bool IsEmpty(MaxHeap H){
        
    	return !H->Size;
    }
    
    // 层序遍历
    void LevelOrderTraversal(MaxHeap H){
        
    	int i;
    	printf("层序遍历的结果是：");
    	for(i = 1;i<=H->Size;i++){
        
    		printf("%d ",H->Elements[i]);
    	} 
    	printf("\n"); 
    } 
    
    int main(){
        
    	MaxHeap H;
    	int MaxSize = 100;
    	H = Create(MaxSize);
    	Insert(H,55);
    	Insert(H,66);
    	Insert(H,44);
    	Insert(H,33);
    	Insert(H,11);
    	Insert(H,22);
    	Insert(H,88);
    	Insert(H,99);
    	/*
    		 99
    		/  \
    	   88  66
    	  / \  / \
    	 55 11 22 44
    	/ 
       33	  
    	*/
    	LevelOrderTraversal(H);
    	DeleteMax(H);
    	LevelOrderTraversal(H);
    	DeleteMax(H);
    	LevelOrderTraversal(H);
    	DeleteMax(H);
    	LevelOrderTraversal(H);
    	DeleteMax(H);
    	LevelOrderTraversal(H);
    	return 0;
    }

### 3. 最小堆的建立 ###

不是初始化堆啦！  
堆的建立：将**已经存在的 N 个元素**按最小堆的要求存放在一个一维数组中

#### 0. 注意 ####

对于一组相同数据，插入建堆和调整建堆建出来的堆也许不一样

#### 1. 插入建堆 ####

通过插入，将 N 个元素一个一个相继插入到一个**初始为空**的堆中去，其时间代价最大是  O ( N l o g N ) O(N logN) O(NlogN)（每次插入是 logN，总共 N 次）

#include<iostream>
    #include<malloc.h>
    const int MinData = -100000;  // 哨兵值
    const int MaxSize = 1005;   // 最大个数 
    using namespace std;
    typedef struct HeapStruct *Heap;
    struct HeapStruct{
        
    	int *data;   // 存值的数组 
    	int size;   // 当前元素个数 
    	int capacity;  // 最大容量 
    };
    
    // 初始化堆
    #include<iostream>
    #include<malloc.h>
    const int MinData = -100000;  // 哨兵值
    const int MaxSize = 1005;   // 最大个数 
    using namespace std;
    typedef struct HeapStruct *Heap;
    struct HeapStruct{
        
    	int *data;   // 存值的数组 
    	int size;   // 当前元素个数 
    	int capacity;  // 最大容量 
    };
    
    // 初始化堆
    Heap Create(){
        
    	Heap H;
    	H = (Heap)malloc(sizeof(struct HeapStruct));
    	H->data = (int *)malloc(sizeof(int) * (MaxSize+1));
    	H->size = 0;
    	H->capacity = MaxSize;
    	H->data[0] = MinData;
    	return H;
    } 
    
    // 插入
    void Insert(Heap H,int x){
        
    	int i = ++H->size;  // 指向数组最后一个 
    	for(;H->data[i/2]>x;i/=2)
    		H->data[i] = H->data[i/2];
    	H->data[i] = x;
    } 
    
    // 遍历 
    void bl(Heap H){
        
    	for(int i=1;i<=H->size;i++)
    		cout<<H->data[i]<<" ";
    }
    
    int main(){
        
    	Heap H;
    	H = Create();
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++){
        
    		int t;
    		cin>>t;
    		Insert(H,t);
    	}
    	bl(H);
    	return 0;
    }

#### 2. 调整建堆 ####

将 N 个元素直接按顺序存入，再调整各结点的位置（简单说来，对于从最后一个有孩子结点的结点来说，其本身结点和孩子结点共同构成"子最小堆"，借助前面删除的想法，对每个"子最小堆"排序，当排序完成，整个最小堆也建立成功），时间代价是  O ( n ) O(n) O(n)

#include<iostream>
    #include<malloc.h>
    const int MinData = -100000;  // 哨兵值
    const int MaxSize = 1005;   // 最大个数 
    using namespace std;
    typedef struct HeapStruct *Heap;
    struct HeapStruct{
        
    	int *data;   // 存值的数组 
    	int size;   // 当前元素个数 
    	int capacity;  // 最大容量 
    };
    
    // 初始化堆
    Heap Create(){
        
    	Heap H;
    	H = (Heap)malloc(sizeof(struct HeapStruct));
    	H->data = (int *)malloc(sizeof(int) * (MaxSize+1));
    	H->size = 0;
    	H->capacity = MaxSize;
    	H->data[0] = MinData;
    	return H;
    } 
    
    // 排序，类似堆的"删除操作" 
    void sort(Heap H,int i){
        
    	int child,parent;
    	int tmp = H->data[i];  // 拿到当前"根结点的值" 
    	for(parent = i;parent*2<=H->size;parent = child){
        
    		child = 2 * parent;
    		if((child!=H->size) && (H->data[child+1] < H->data[child]))
    			child++;
    		if(H->data[child] >= tmp)
    			break;
    		else
    			H->data[parent] = H->data[child]; 
    	}
    	H->data[parent] = tmp;
    }
    // 调整
    void adjust(Heap H){
        
    	int i= H->size/2;
    	for(;i>0;i--){
        
    		// 以每个有孩子结点的结点作为根结点，对其子树进行堆排序 
    		sort(H,i);
    	}
    } 
    
    // 遍历 
    void bl(Heap H){
        
    	for(int i=1;i<=H->size;i++){
        
    		cout<<H->data[i]<<" ";
    	}
    	cout<<endl;
    }
    
    
    int main(){
        
    	Heap H;
    	H = Create();
    	int n;
    	cin>>n;
    	for(int i=0;i<n;i++)
    		cin>>H->data[++H->size];
    	adjust(H);
    	bl(H); 
    	return 0;
    }

[20181104104440648.jpg]: /images/20220422/09f5d69bdf5a49d390f01aac3887b65e.png
[20181104104459868.jpg]: /images/20220422/2b20a151256f41b3aa40fd64d2f3dba6.png
[20181104104516209.jpg]: /images/20220422/8fdb1931a49a41088189da4923c35a8c.png
[20181104104530440.jpg]: /images/20220422/31944a3cf7d14871893c7465588d3bcf.png