数据结构——最大堆最小堆

淡淡的烟草味﹌ 2022-10-05 14:54 231阅读 0赞

**定义：**  
最大堆和最小堆都是一棵完全二叉树。

最大堆：是指根节点的关键字值是堆中的最大关键字值，且每个节点若有儿子节点，其关键字值都不小于其儿子节点的关键字值。

最小堆：是指根节点的关键字值是堆中的最小关键字值，且每个节点若有儿子节点，其关键字值都不大于其儿子节点的关键字值。

最大堆的插入操作  
步骤：

1 把待增加的节点编号 i 设置为已知堆的总节点数加 1 即 i=++(\*n)，因此，新增的元素放在最下一层作为新的叶子节点。求出节点 i 的父节点 parent=i/2; 判断是否为空堆，并比较所插入元素与父节点关键字值的大小；  
2 若所插入节点关键字值大于父节点关键字值即item>heap\[parent\],则把父节点向下移,并把父节点作为当前节点，依次求父节点，即依次沿着树枝向上延伸直到根节点；  
3 把元素item插入到正确位置；

**最大堆的删除操作**  
最大堆的删除，即删除最大的元素。我们先取最后的元素提到根结点，然后删除最大值，然后再把新的根节点放到合适的位置。

首先删除根节点，并把最后一个节点临时作为新的根节点，将新的根节点作为当前节点与其孩子节点中最大的关键值节点进行比较，若小于其孩子节点的关键值，则与其孩子节点进行交换位置，并把新位置作为当前节点继续与其孩子节点进行比较，一直延伸下去，直到没有孩子节点为止；

***最大堆***

#include <iostream>
    using namespace std;
    class HeapNode
    {
        
    public:
    	operator double() const{
        return data;}
    	int operator <= (HeapNode hn) const{
        return data<=hn.data;	}
    	int operator <	(HeapNode hn) const{
        return data<hn.data;	}
    	int operator >= (HeapNode hn) const{
        return data>=hn.data;	}
    	int operator >	(HeapNode hn) const{
        return data>hn.data;	}
    	int operator == (HeapNode hn) const{
        return data==hn.data;	}
        HeapNode(){
        }
        HeapNode(int id,double d)
        {
        
            ID=id;
            data=d;
        }
        int ID;
        double data;
    };
    
    class MaxHeap
    {
        
    public:
    	MaxHeap(int n);    //构造函数，N表示堆中能存储的最大元素的个数 
    	void Insert(HeapNode heapNode);  //向堆中插入一个结点 
    	void DeleteMax(HeapNode &heapNode);  //删除堆中的最大结点 
    private:
    	int size;            
    	HeapNode *MH;       
    	
    	void Delete(HeapNode &heapNode,int index);  //删除堆中标号为index的元素，index从1开始，即1表示最大元素 
    	void SiftUp(int index);          //将堆中标号为index的元素，向上调整，保证堆结构 
    	void SiftDown(int index);      //将堆中标号为index的元素，向下调整，保证堆结构 
    };
    
    MaxHeap::MaxHeap(int n)
    {
        
    	size=0;
    	MH=new HeapNode[n];
    }
    
    void MaxHeap::SiftUp(int index)
    {
        
    	if(index<=1)
    		return;
    	bool done=false;
    	do
    	{
        
    		if(MH[index]>MH[index/2])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    		
    		index=index/2;
    	}while(index>1&&!done);
    }
    
    void MaxHeap::SiftDown(int index)
    {
        
    	if(2*index>size)
    		return;
    	bool done=false;
    	do
    	{
        
    		index=2*index;
    		if(index+1<=size&&MH[index+1]>MH[index])
    			index=index+1;
    		if(MH[index/2]<MH[index])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    	}while(2*index<=size&&!done);
    }
    
    void MaxHeap::Insert(HeapNode heapNode)
    {
        
    	size+=1;
    	MH[size]=heapNode;
    	SiftUp(size);
    }
    
    void MaxHeap::Delete(HeapNode &heapNode,int index)
    {
        
    	if(index<1||index>size)
    	{
        
    		return;
    	}
    	HeapNode x=MH[index],y=MH[size];
    	heapNode=MH[index];
    	size-=1;
    	if(index==size+1)
    		return;
    	MH[index]=y;//将原来堆中的最后一个放到要被删除的位置，再继续调整堆 
    	if(y>=x)
    		SiftUp(index);
    	else
    		SiftDown(index);
    }
    
    void MaxHeap::DeleteMax(HeapNode &heapNode)
    {
        
    	Delete(heapNode,1);
    }
    int main()
    {
        
        double data[]={
        13,3,4,2,6,15,67,21,88};
    
        MaxHeap *Maxhp=new MaxHeap(100);
        for(int i=0;i<9;i++)
        {
        
            HeapNode hp(i+1,data[i]);
            Maxhp->Insert(hp);
        }
        for(int i=1;i<=9;i++)
        {
          HeapNode hp2;
           Maxhp->DeleteMax(hp2);
            cout<<hp2.data<<'\t';
        }
        
        return 0;
    }

![在这里插入图片描述][20210609200553453.png]  
***最小堆***

#include <iostream>
    using namespace std;
    class HeapNode
    {
        
    public:
    	operator double() const{
        return data;}
    	int operator <= (HeapNode hn) const{
        return data<=hn.data;	}
    	int operator <	(HeapNode hn) const{
        return data<hn.data;	}
    	int operator >= (HeapNode hn) const{
        return data>=hn.data;	}
    	int operator >	(HeapNode hn) const{
        return data>hn.data;	}
    	int operator == (HeapNode hn) const{
        return data==hn.data;	}
        HeapNode(){
        }
        HeapNode(int id,double d)
        {
        
            ID=id;
            data=d;
        }
        int ID;
        double data;
    };
    
    class MinHeap
    {
        
    public:
    	MinHeap(int n);
    	void Insert(HeapNode heapNode);
    	void DeleteMin(HeapNode &heapNode);
    private:
    	int size;
    	HeapNode *MH;
    	
    	void Delete(HeapNode &heapNode,int index);
    	void SiftUp(int index);
    	void SiftDown(int index);
    };
    
    MinHeap::MinHeap(int n)
    {
        
    	size=0;
    	MH=new HeapNode[n];
    }
    
    void MinHeap::SiftUp(int index)
    {
        
    	if(index<=1)
    		return;
    	bool done=false;
    	do
    	{
        
    		if(MH[index]<MH[index/2])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    		index=index/2;
    	}while(index>1&&!done);
    }
    
    void MinHeap::SiftDown(int index)
    {
        
    	if(2*index>size)
    		return;
    	bool done=false;
    	do
    	{
        
    		index=2*index;
    		if(index+1<=size&&MH[index+1]<MH[index])
    			index=index+1;
    		if(MH[index/2]>MH[index])
    		{
        
    			HeapNode tmp=MH[index];
    			MH[index]=MH[index/2];
    			MH[index/2]=tmp;
    		}
    		else
    			done=true;
    	}while(2*index<=size&&!done);
    }
    
    void MinHeap::Insert(HeapNode heapNode)
    {
        
    	size+=1;
    	MH[size]=heapNode;
    	SiftUp(size);
    }
    
    void MinHeap::Delete(HeapNode &heapNode,int index)
    {
        
    	if(index<1||index>size)
    	{
        
    		return;
    	}
    	HeapNode x=MH[index],y=MH[size];
    	heapNode=MH[index];
    	size-=1;
    	if(index==size+1)
    		return;
    	MH[index]=y;
    	if(y<=x)
    		SiftUp(index);
    	else
    		SiftDown(index);
    }
    
    void MinHeap::DeleteMin(HeapNode &heapNode)
    {
        
    	Delete(heapNode,1);
    }
    int main()
    {
        
        double data[]={
        13,3,4,2,6,15,67,21,88};
    
        MinHeap *Minhp=new MinHeap(100);
        for(int i=0;i<9;i++)
        {
        
            HeapNode hp(i+1,data[i]);
            Minhp->Insert(hp);
        }
        for(int i=1;i<=9;i++)
        {
          HeapNode hp2;
           Minhp->DeleteMin(hp2);
            cout<<hp2.data<<'\t';
        }
        
        return 0;
    }

![在这里插入图片描述][20210609200700282.png]

[20210609200553453.png]: /images/20221005/e76b41261ec54c56af97979f2ccd6e5a.png
[20210609200700282.png]: /images/20221005/307ac764f5f3431fac0242228796529c.png