学习：堆排序（大顶堆）

阳光穿透心脏的1/2处 2023-03-13 02:19 19阅读 0赞

## 学习：堆排序（大顶堆） ##

#include <iostream>
    #include <cassert>
    #include <ctime>
    #include <cstdlib>
    using namespace std;
    
    template <class T>
    class MaxHeap
    { 
    	private:
    		T *data;
    		int count;
    		int capacity;
    		
    		void shiftUp(int k)
    		{ 
    			while(k>1 && data[k/2] < data[k])//不是根节点，且父节点的值小于当前结点的值 
    			{ 
    				swap(data[k/2] , data[k]);
    				k/=2; 
    			}
    		}
    		
    		void shiftDown(int k)
    		{ 
    			while( 2*k <= count)//有孩子
    			{ 
    				int j=k*2;//左孩子
    				if(j+1 <= count && data[j+1] > data[j])//有右孩子且右孩子的值大于左孩子的值
    					j+=1;
    				if(data[k] >= data[j])
    					break;
    				swap(data[k] , data[j]); 
    				k=j;
    			}
    		}
    	public:
    		MaxHeap(int capacity)
    		{ 
    			data = new T[capacity+1];
    			count = 0;//当前堆中结点个数 
    			this->capacity = capacity; 
    		}
    		~MaxHeap()
    		{ 
    			delete[] data;	
    		}
    		int size() const
    		{ 
    			return count;
    		}
    		bool isEmpty() const
    		{ 
    			return count == 0;
    		}
    		bool isFull()
    		{ 
    			return count == capacity-1;
    		}
    		void insert(T item)
    		{ 
    			assert( !isFull() );
    			data[++count]=item;
    			shiftUp(count);
    		}
    		T remove()
    		{ 
    			assert( !isEmpty() );
    			T temp=data[1];
    			swap(data[1], data[count]);
    			count--;
    			shiftDown(1);
    			return temp;
    		}
    		void print() const
    		{ 
    			for(int i=1; i<=count; i++)
    				cout<<data[i]<<" ";
    			cout<<endl;
    		}
    }; 
    
    int main()
    { 
    	MaxHeap<int> maxHeap(50);
    	srand(time(NULL));
    	for(int i=0; i<15; i++)
    		maxHeap.insert( rand()%100 );
    	maxHeap.print();
    	for(int i=0; i<15; i++)
    		cout<<maxHeap.remove()<<" ";
    	cout<<endl;
    	return 0;
    }