C++实现大顶堆(插入，删除)-白红宇

C++实现大顶堆(插入，删除)

阅读量：6593 次

发布时间：2019-06-24

本文共 1794 字，大约阅读时间需要 5 分钟。

practice Max.h文件

#ifndef PRACTICE_MAX_H_INCLUDED#define PRACTICE_MAX_H_INCLUDEDtemplate 
     
      class MaxHeap{public:      MaxHeap(int mx=100);      virtual ~MaxHeap();      bool IsEmpty();      void Push(const T& e);      void Pop();      const T& Top() const;private:    T* heapArray;    int maxSize;    int currentSize;    void trickleUp(int index);    void trickleDown(int index);};template
      
       MaxHeap
       
        ::MaxHeap(int mx){    if(mx<1) throw"max size must be>1";    maxSize=mx;    currentSize=0;    heapArray=new T[maxSize];}template
        
         MaxHeap
         
          ::~MaxHeap(){    delete[] heapArray;}template
          
           bool MaxHeap
           
            ::IsEmpty(){ return currentSize==0;}template
            
             void MaxHeap
             
              ::Push(const T& e) //插入一个值{ if(currentSize==maxSize) throw"MaxHeap is full"; heapArray[currentSize]=e; trickleUp(currentSize); currentSize++;}template 
              
               void MaxHeap
               
                ::trickleUp(int index)//向上渗透¸{ int parent=(index-1)/2; T bottom=heapArray[index]; while(index>0&&heapArray[parent]
                
                 const T & MaxHeap
                 
                  ::Top() const//取出第一个值{ return heapArray[0];}template 
                  
                   void MaxHeap
                   
                    ::Pop(){ heapArray[0]=heapArray[--currentSize]; trickleDown(0);}template
                    
                     void MaxHeap
                     
                      ::trickleDown(int index)//先下渗透{ int largerChild; T top=heapArray[index]; while(index
                      
                       =heapArray[largerChild]) break; heapArray[index]=heapArray[largerChild]; index=largerChild; } heapArray[index]=top;}#endif // PRACTICE_MAX_H_INCLUDED

practice.cpp文件

#include
     
      #include"practice Max.h"using namespace std;    int main()    {        MaxHeap
      
        h(100);//        h.Push(20);//         h.Push(30);//          h.Push(40); h.Push(50);//          h.Push(90);//          cout<
       
        <