C++排序（小堆排序）

概述C++排序（小堆排序）

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

    #include<iostream>      #include<string>      using namespace std;            template<class Type>      class MinHeap      {      public:          MinHeap(int sz=DefaultSize)          {              capacity = sz>DefaultSize?sz:DefaultSize;              heap = new Type[capacity];              size = 0;          }          MinHeap(Type ar[],int n)          {              capacity = n>DefaultSize?n:DefaultSize;              heap = new Type[capacity];              for(int i=0; i<n; ++i)              {                  heap[i] = ar[i];              }              size = n;                    int pos = n/2-1;              while(pos >= 0)              {                  SiftDown(pos,n-1);                  pos--;              }          }          ~MinHeap()          {              delete []heap;              heap = NulL;          }          voID Show()const          {              for(int i=0; i<size; ++i)              {                  cout<<heap[i]<<" ";              }              cout<<endl;          }          bool IsEmpty()const          {              return size == 0;          }          bool IsFull()const          {              return size >= capacity;          }          voID MakeHeap()          {              size = 0;          }          Type ReMoveMin()          {              Type tmp = heap[0];              heap[0] = heap[size-1];              size--;              SiftDown(0,size-1);              return tmp;          }          voID Sort()          {              Type *data = new Type[size];              int i = 0;              while(!IsEmpty())              {                  data[i++] = ReMoveMin();              }                    size = i;              for(i=0; i<size; ++i)              {                  heap[i] = data[i];              }              delete []data;              data = NulL;          }          voID Insert(const Type &x)          {              heap[size] = x;              SiftUp(size);              size++;          }            private:          voID SiftUp(int start)          {              int j = start;              int i = (j-1)/2;                    Type tmp = heap[j];                    while(j>0)              {                  if(tmp > heap[i])                      break;                  else                  {                      heap[j] = heap[i];                      j = i;                      i = (j-1)/2;                  }              }              heap[j] = tmp;          }          voID SiftDown(int start,int end)          {              int i = start;              int j = 2*i+1;                    Type temp = heap[i];                    while(j <= end)              {                  if(j<end && heap[j] > heap[j+1])                      j = j+1;                  if(temp < heap[j])                      break;                  else                  {                      heap[i] = heap[j];                      i = j;                      j = 2*i+1;                  }              }              heap[i] = temp;          }            private:          enum{DefaultSize = 10};          Type *heap;          int capacity;          int size;      };  

堆可以被看作是一个完全二叉树，小堆排序利用小根堆堆顶记录的关键字最小这一个特征，使得从当前无序区中选取最小关键字并进一步记录 *** 作变的简单。 @H_502_8@

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的C++排序（小堆排序）全部内容，希望文章能够帮你解决C++排序（小堆排序）所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。