数据结构——最小堆的实现总结

￡神魔★判官ぃ 2022-06-04 02:06 220阅读 0赞

**堆的实用性**  
编程过程中，时常会遇到一种模型，我们收集到一些数据，并对其处理，但是我们需要首先处理这些数据中具有最小关键码或者最大关键码（Key：可以是根据数据的先后顺序或重要程度等给数据编的号码）的数据。我们希望有一种数据结构能够支持插入操作并能方便的从中取出具有最小或最大关键码的记录，这样的数据结构即为**优先级队列**，优先级队里的实现方式有多种，其中最高效的一种便是堆(heap)。

**堆的种类**  
堆有最大堆和最小堆两种。其名字很形象，上面的元素小，越向下元素越大，在取堆顶元素的时候总是先拿到最小的，最大堆与之相反。  
这里主要**通过完全二叉树的数组存储结构来实现最小堆**。为何用这种结构？通过对堆的各项操作的分析，不难发现，通过完全二叉树的结构对元素的定位、数据的调整等方面都可以提高效率和写代码的方便程度。（结合下面的代码更容易体会的到！）

**关键操作实现一——建立堆**  
在下面的代码中heap class有两个构造函数，都可以用来建立一个heap。

> 构造函数1：通过输入堆顺序的数据来建立heap  
> 构造函数2：通过copy一个数组数据（不一定具有heap的数据顺序），通过元素顺序调整建立heap

第一种当然没什么好说的。下面看一下第二种实现方式的原理，这种方式运用了两个关键的私有函数：siftDown()与siftUp()，一个是下滑调整为最小堆，另一个是上上滑调整为最小堆。  
siftDown()函数的主要实现思路是：

> (1)借助完全二叉树的节点排布规律，即可用通过公式currentPosition = （currentSize - 2） / 2得到最后一个分支节点（最后一个含有孩子的节点）。  
> (2)从此分支节点开始把当前节点数据与其孩子中较小的数据比较，如果孩子数据小于当前节点的数据，则应该交换（最小堆，小的数据应该上浮）。  
> (3)交换完成后，其孩子的数据变大了，那么应该考虑其孩子那一层是否符合最小堆的数据排列形式。（也就是一个循环的过程）

用这种叙述来描述这一过程太难了，搭配上下面的过程图应该会比较好理解些！  
![初始化][format_png]

![过程][format_png 1]  
在这个过程中，首先根据二叉树的分布规律（就是我前面说的那样），用（8 - 2）/2 = 3找到下标是3的节点，这里就是09元素。那么用09与23比较，不需要交换，通过计数器 i - 1（结合代码）可以移动到上一个节点，也就是78（下标是3 - 1 = 2），然后同样与其孩子中最小的比较，这时候发现78 > 65，也就是应该交换，交换完成（注意这个时候如果子节点下面还有节点，就不把78这个数据放入子节点了，而是继续比较）。  
在第5步的时候，53与09交换后，09仍有子节点，所以53先不放到09的位置，（就是我上面说的那种情况）而是直接和17比较，如法炮制……。

**关键操作实现二——插入与删除元素**

无论是向堆中插入元素还是删除元素，都应该让操作后的集合仍然保持堆的数据结构（即上小下大）。

> 插入元素：  
> 首先把元素放入数组的最后，然后通过与sitfDown()方向相反的操作siftUp()对插入元素进行顺序调整。两个函数的实现方式相似，只不过方向相反。  
> 删除元素：  
> 因为删除的始终是堆顶，那么可以把最后一个元素放到堆顶进行覆盖，然后调用siftDown()（主要这个时候堆的大小：size - 1）,对堆进行一次数据调整即可。

下面是整个堆类的实现代码：

/*
    *最小堆(heap)类定义
    *By Xiuyu Zhu 9:10 2017/12/1 
    *Reference by Renkun Yin's book
    */
    #include <iostream>
    #define DefaultSize 10
    
    template<class E>
    class MinHeap {
    public:
    	MinHeap(int sz = DefaultSize);	//构造函数：建立空堆
    	MinHeap(E arr[], int n);		//构造函数：通过一个数组创建堆
    	~MinHeap() { delete[] heap; }	//析构函数
    	bool insert(const E& x);		//将x插入到最小堆中
    	bool removeMin(E& x);			//删除堆顶元素(min value)
    	bool isEmpty() const;			//判断堆是否是空
    	bool isFull() const;			//判断堆是否已满
    	void makeEmpty();				//置空堆 
    	void output();					//数组元素输出
    private:
    	E* heap;						//存放最小堆元素的数组
    	int currentSize;				//最小堆中当前元素的个数
    	int maxHeapSize;				//最小堆最多存放元素个数
    	void siftDown(int start, int m);//从start到m下滑调整为最小堆
    	void siftUp(int start);			//从start到0上滑调整为最小堆
    };
    
    //函数定义
    template<class E>
    MinHeap<E>::MinHeap(int sz) {
    	//方式1建立最小堆，动态创建
    	maxHeapSize = (DefaultSize < sz) ? sz : DefaultSize;
    	heap = new E[maxHeapSize];
    	if (nullptr == heap) {
    		std::cerr << "内存分配失败" << std::endl;
    		exit(EXIT_FAILURE);
    	}
    	currentSize = 0;
    }
    
    template<class E>
    MinHeap<E>::MinHeap(E arr[], int n) {
    	//方式2创建最小堆，从已知数组中复制数据，然后调整为最小堆结构
    	//函数参数：已知数组数据、数据个数
    	maxHeapSize = (DefaultSize < n) ? n : DefaultSize;
    	heap = new E[maxHeapSize];
    	if (nullptr == heap) {
    		std::cerr << "内存分配失败" << std::endl;
    		exit(EXIT_FAILURE);
    	}
    	for (int i = 0; i < n; i ++) {
    		heap[i] = arr[i];							//数据copy
    	}
    	currentSize = n;
    	//利用完全二叉树中元素的排列规律，找到最初调整位置，也就是最后的分支节点
    	int currentPos = (currentSize - 1) / 2;			
    	while (currentPos >= 0)	{						//自底向上逐步扩大形成堆
    		siftDown(currentPos, currentSize - 1);		//局部调整
    		currentPos--;								//向前换一个分支节点
    	}
    }
    
    template<class E>
    void MinHeap<E>::output() {
    	//循环输出堆数组元素
    	for (int i = 0; i < currentSize; i ++) {
    		std::cout << heap[i] << ' ';
    	}
    }
    
    template<class E>
    bool MinHeap<E>::isEmpty() const {
    	//判断heap是否是空
    	return (0 == currentSize) ? true : false;
    }
    
    template<class E>
    bool MinHeap<E>::isFull() const {
    	//判断heap是否已经满
    	return (maxHeapSize == currentSize) ? true : false;
    }
    
    template<class E>
    void MinHeap<E>::makeEmpty() {
    	currentSize = 0;
    }
    
    template<class E>
    bool MinHeap<E>::insert(const E& x) {
    	//共有函数：将x插入到最小堆中
    	if (isFull()) {									//判断堆是否已经满
    		std::cerr << "Heap Fulled" << std::endl;
    		return false;								
    	}
    	heap[currentSize] = x;							//将x元素插入到数组最后
    	siftUp(currentSize);
    	currentSize++;									//对当前大小增加1
    	return true;
    }
    
    template<class E>
    bool MinHeap<E>::removeMin(E& x) {
    	//删除堆顶元素，引用返回
    	if (0 == currentSize) {
    		std::cout << "Heap Emptyed" << std::endl;
    		return false;
    	}
    	x = heap[0];
    	heap[0] = heap[currentSize - 1];
    	currentSize--;
    	siftDown(0, currentSize - 1);					//借助函数对堆再一次调整
    	return true;
    }
    
    template<class E>
    void MinHeap<E>::siftDown(int start, int m) {
    	//私有函数：从节点start开始到m为止，自上向下比较，如果子女值小于父节点的值，
    	//则关键码小的上浮，继续向下层比较，这样将一个集合的局部调整为最小堆
    	int i = start;
    	int j = 2 * i + 1;								//通过公式2x+1求得x左子女位置
    	E temp = heap[i];								//temp记录原来的的数据
    	while (j <= m) {
    		if (j < m && heap[j] > heap[j + 1]) {
    			j = j + 1;								//j指向左右子女中较小的一个
    		}
    		if (heap[j] >= temp) {
    			break;									//已经符合最小堆的结构，无需调整
    		}
    		else {										//否则调整，并更新i，j至下一层
    			heap[i] = heap[j];						
    			i = j;
    			j = 2 * i + 1;
    		}
    	}
    	heap[i] = temp;									//完成调整后的数据交换
    }
    
    template<class E>
    void MinHeap<E>::siftUp(int start) {
    	//私有函数：从节点start开始到节点0为止，自下向上比较，如果子女的值小于父节点的值
    	//则相互交换，这样讲集合重新调整为最小堆(注意比较元素E的逻辑运算符重载)
    	int j = start;
    	int i = (j - 1) / 2;								//找左子女公式的逆运算公式
    	E temp = heap[j];
    	while (j > 0) {
    		if (heap[i] <= temp) {
    			break;
    		}
    		else {
    			heap[j] = heap[i];
    			j = i;
    			i = (j - 1) / 2;
    		}
    	}
    	heap[j] = temp;
    }

下面是函数测试代码及测试结果：

/*
    *Min Heap 测试代码
    */
    #include "heap.h"
    using namespace std;
    
    int main()
    {
    	int data[8] {0};
    	
    	//用数组数据建最小堆测试
    	for (int i = 0; i < 8; i ++) {
    		cin >> data[i];
    	}
    	MinHeap<int> minheap(data, 8);
    	minheap.output();
    	cout << endl;
    
    	//向堆内插入元素测试
    	int value{11};
    	minheap.insert(value);
    	minheap.output();
    	cout << endl;
    
    	//从堆内删除元素测试
    	int delValue{ 0 };
    	minheap.removeMin(delValue);
    	minheap.output();
    	cout << endl;
    
    	system("pause");
    	return 0;
    }

\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-gehEp2xP-1571447839778)(https://img-blog.csdn.net/20171201135149329?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvd2VpeGluXzM3ODE4MDgx/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast)\]

大概过程就是这样，当然说的不是很清楚，，但是可以通过过程图和代码自己梳理清楚。也希望大家可以在讨论区补充！  
**想一起解决编程中遇到的麻烦吗？想一起学习更多软件知识吗？想找一群志同道合的朋友吗？想找到自己关于计算机真正的兴趣所在吗？那就加入我们吧！（老学长公众号刚刚开通不久，每隔3天会发表一篇有质量的文章，希望大家多支持！）**  
![公众号：奇妙的coco][coco]

[format_png]: /images/20220604/c1393b16ae344487858b857a464a1d72.png
[format_png 1]: /images/20220604/7f02a278f288461bae181d446cc95975.png
[coco]: /images/20220604/a38f3f29f508492ca7100bb530bcbbd0.png