//heap.h

/*

堆最好是以数组的形式存储的

书上P86页

注释和最后一段是我写的

*/


//using namespace std;


template

void AdjustDown (T heap[],int r,int j)  //单次向下调整最小堆

{

   int child=2*r+1;

   T temp=heap[r];

   while (child<=j) {

       if ((childheap[child+1])) child++;  //选出左右两个孩子中最小的那个

       if (temp<=heap[child]) break;   //若根小于其左右孩子,则跳出

       heap[(child-1)/2]=heap[child];  //把左右孩子中小的元素放到根的位置

       child=2*child+1;    //开始搜索下一层左右孩子,依旧跟第一个根r相比

   }

   heap[(child-1)/2]=temp; //把最后交换出的空余位置放根r

}


template

void AdjustMinHeap(T heap[],int n)  //整堆调整为最小堆,n为元素的个数,i从下往上开始调整

{

   for (int i=(n-2)/2;i>-1;i–) AdjustDown(heap,i,n-1);

}


template

void PrintHeap(T heap[],int n)  //打印整堆,n为元素的个数,

{

   for (int i=0;i

   std::cout<

}

 

 

 

 

 

//Untitled.cpp

#include

#include “heap.h”


using namespace std;


int main()

{

   int test[]={71,74,2,72,54,93,52,28};

   int n=8;

   PrintHeap(test,n);

   AdjustMinHeap(test,n);

   PrintHeap(test,n);

}

》上有1条评论

  1. Pingback引用通告: BZ编程小组 作品 | BZ编程小组

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.