数据结构堆的实现

短命女 2022-08-04 12:46 184阅读 0赞

## 堆的概念 ##

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：  
堆中某个节点的值总是不大于或不小于其父节点的值；  
**堆总是一棵完全二叉树** **。**  
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。  
堆的定义如下：n个元素的序列\{k1,k2,ki,…,kn\}当且仅当满足下关系时，称之为堆。  
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)  
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列\{k1,k2,…,kn\}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。

堆的二叉树和数组表示如下，注意数组下标从1开始，这样对于下标为k的元素a\[k\]，如果其存在父节点，其父节点就可表示为a\[k/2\]，k/2取整数。

![Center][]

## 堆的操作 ##

三个问题：

堆的插入

堆的调整

建堆

堆的插入

将一个新元素插入建好的堆中

![Center 1][]

建堆

![Center 2][]

不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：  
（1） R的值小于或等于其两个子女，此时堆已完成；  
（2） R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。

下图展示了建堆过程

![Center 3][]

建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程。上图依次以87、72、83为父节点调整。87只有一个儿子9,9比87小，不用调整;然后72有两个儿子30、49，都比72小，不用调整;然后83有两个儿子，91最大且大于83,这样就要把83提下来，91升上去。

![Center 4][]

然后是节点43,43比87小，43提下去，87升上来，43比9大，不用调整;然后是66,两个儿子91和72都比66大，和较大的91交换位置，66下去，91上来，然后66又比83小，66下去，83上来;然后是节点79,79的两个儿子91和87都比它大，91上去，79下来，然后79有两个儿子，83和72,83大于79,83上去，79下来，然后79的两个儿子55和66都比79小，结束。

调整

每次从堆顶取走最大值或最小值后要使剩余的元素成堆，如何调整呢？可以将最后一个元素推到堆顶，然后自堆顶向下调整，和建堆时的调整类似，就不多说了。

## 堆的实现 ##

// heap.cpp : 定义控制台应用程序的入口点。
    //
    
    #include "stdafx.h"
    #include<vector>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    
    #define LARGENUM 1000000
    
    
    class Heap
    {
    private:
    	vector<int> array;
    
    	int find(int tofind)
    	{
    		vector<int>::iterator it;
    		it = std::find(array.begin(), array.end(), tofind);
    		return it == array.end() ? -1 : it - array.begin();
    	}
    public:
    	Heap()//构造
    	{
    		array.push_back(LARGENUM);//哨兵
    	}
    
    	void insert(const int val)//插入
    	{
    		_ASSERTE(val < LARGENUM);
    		array.push_back(val);
    		int index = array.size() - 1;
    		while (array[index] > array[index / 2])
    		{
    			array[index] = array[index/ 2];
    			array[index / 2] = val;
    			index = index / 2;
    		}
    	}
    
    	bool erase(int val)//删除
    	{
    		int index = find(val);
    		if (index < 0)
    			return false;
    		array[index] = array.back();
    		array.pop_back();
    		while (index * 2 < array.size())
    		{
    			int t = array[index];
    			if (2 * index + 1 < array.size())
    			{
    				if (array[index] > array[2 * index] && array[index] > array[2 * index + 1])
    					return true;
    				int nn = array[2 * index + 1] > array[2 * index] ? 2 * index + 1 : 2 * index;
    				array[index] = array[nn];
    				array[nn] = t;
    				index = nn;
    			}
    			else
    			{
    				if (array[index] > array[2 * index])
    					return true;
    				int t = array[index];
    				array[index] = array[2 * index];
    				array[2 * index] = t;
    				return true;
    			}
    
    		}
    		
    	}
    
    	int top()//返回堆顶
    	{
    		_ASSERTE(array.size() != 1);
    		return  array[1];
    	}
    
    	void pop()//弹出堆顶
    	{
    		_ASSERTE(array.size() != 1);
    		array[1] = array.back();
    		array.pop_back();
    		int index = 1;
    		
    		while (index * 2 < array.size())
    		{
    			int t = array[index];
    			if (2 * index + 1 < array.size())
    			{
    				if (array[index] > array[2 * index] && array[index] > array[2 * index + 1])
    					return;
    
    				int nn = array[2 * index + 1] > array[2 * index] ? 2 * index + 1 : 2 * index;
    				array[index] = array[nn];
    				array[nn] = t;
    				index = nn;
    			}
    			else
    			{
    				if (array[index] > array[2 * index])
    					return;
    				int t = array[index];
    				array[index] = array[2 * index];
    				array[2 * index] = t;
    				return;
    			}
    
    		}
    	}
    
    	
    	bool empty()
    	{
    		return array.size() == 1;
    	}
    
    	int size()//返回堆的大小
    	{
    		return array.size() - 1;
    	}
    
    };
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	
    	Heap h;
    	h.insert(10);
    	h.insert(35);
    	h.insert(19);
    	h.insert(5); 
    	h.insert(2); 
    	h.insert(51);
    	h.insert(37);
    	h.insert(7);
    	h.insert(45);
    	h.insert(63);
    	cout << h.size() << endl;
    	cout << h.top()<< endl;
    	h.pop();
    	cout << h.size() << endl;
    	cout << h.top() << endl;
    	h.erase(45);
    
    	system("pause");
    	return 0;
    }

stl没有直接的堆数据结构，不过可以用algorithm头文件里的算法以vector为底层数据结构构建堆

#include "stdafx.h"
    #include <iostream>  
    #include <algorithm>  
    #include <vector>  
    using namespace std;
    bool cmp(int a, int b) //比较函数
    {
    	return a > b;
    }
    int main()
    {
    	int myints[] = { 10, 20, 30, 5, 15 };
    	vector<int> v(myints, myints + 5);
    	vector<int>::iterator it;
    	make_heap(v.begin(), v.end(),cmp);//male_heap就是构造一棵树，使得每个父结点均大于等于其子女结点  
    	cout << "initial max heap   : " << v.front() << endl;
    	/* */
    	pop_heap(v.begin(), v.end(),cmp);//pop_heap不是删除某个元素而是把第一个和最后一个元素对调后[first,end-1]进行构树，最后一个不进行构树  
    	v.pop_back();//删除最后一个的结点  
    	cout << "max heap after pop : " << v.front() << endl;
    	v.push_back(99);//在最后增加一个结点  
    	push_heap(v.begin(), v.end(),cmp);//重新构树  
    	cout << "max heap after push: " << v.front() << endl;
    	sort_heap(v.begin(), v.end(),cmp);//把树的结点的权值进行排序  
    	/*for(int j=0;j<v.size();j++)
    	cout<<v[j]<<' ';
    	cout<<endl;*/
    	cout << "final sorted range :";
    	for (unsigned i = 0; i<v.size(); i++)
    		cout << " " << v[i];
    	cout << endl;
    	return 0;
    }

cmp为比较函数，可选。

[Center]: /images/20220731/f97aaede6c5c46d9a26b09727355b3f8.png
[Center 1]: /images/20220731/73a551f0a43146c8aaa7d3eb89822919.png
[Center 2]: /images/20220731/1a64bfbb78d94ac386eba4e3a2264db4.png
[Center 3]: /images/20220731/57d900d8a737441f829fc10cfbfe144e.png
[Center 4]: /images/20220731/7498d1dbd9b1437d913109a81bd98d6c.png