狂奔的蜗牛

通过计算机成就人生

C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 1 Comments :: 0 Trackbacks
  1 #include <iostream>
  2 using namespace std;
  3 
  4 class suanfa {
  5 public:
  6     int tempsize;
  7     suanfa(int heapsize);
  8     /*将a[i]为根节点的子树生成最大堆!*/
  9     void heapify(int* a, int i);
 10     /*获取父节点,在这里没用*/
 11     int parent(int i);
 12     /*获取左子树,数组序号*/
 13     int left(int i);
 14     /*获取右子树,数组序号*/
 15     int right(int i);
 16     /*交换2个值*/
 17     void swap(int *a ,int i, int j);
 18     /*暂时先不用--日后再用*/
 19     void max_heapify(int* a, int heapsize);
 20     /*堆排序*/
 21     void  heapify_sort(int* a, int size);
 22     ~suanfa();
 23 };
 24 suanfa::suanfa(int heapsize){
 25     tempsize = heapsize;
 26 }
 27 int suanfa::left(int i){
 28     return 2*+ 1;
 29 }
 30 int suanfa::right(int i){
 31     return 2*i+2;
 32 }
 33 int suanfa::parent(int i){
 34     return i/2;
 35 }
 36 
 37 suanfa::~suanfa(){
 38     //delete [] a;
 39     //m_array = NULL;
 40     cout << "我被析构了" << endl;
 41 }
 42 void suanfa::heapify(int* a, int i){
 43     int l = left(i);
 44     int r = right(i);
 45     int largest = 0;//以a[i]为根节点的子树的最大值的数组下标
 46     int size = tempsize;//heapsize 这里=数组的大小
 47     /**获取该子树最大下标*/
 48     if (l > size -1) {
 49         l = size -1;
 50     }
 51     if(r > size -1){
 52         r = size -1;
 53     }
 54     if (l <= size - 1  && a[l] > a[i]) {
 55         largest = l;
 56     }else {
 57         largest = r;
 58     }
 59     if (r <= size - 1 && a[r] > a[largest]) {
 60         largest = r;
 61     }
 62     /*如果根节点不是改子数组最大值,则进行交换*/
 63     if (a[i] < a[largest]) {
 64         swap(a, i, largest);
 65         heapify(a, largest);
 66     }
 67 
 68     
 69 }
 70 void suanfa::swap(int* a, int i, int j){
 71     int key = a[i];
 72     a[i] = a[j];
 73     a[j] = key;
 74 }
 75 void suanfa::max_heapify(int* a, int heapsize){
 76     //j->(heapsize-1)/2的子数组是最大堆.
 77     for(int j = (heapsize - 1/ 2; j >=0--j)
 78     {
 79         heapify(a,j);
 80     }
 81 }
 82 void suanfa::heapify_sort(int* a, int size){
 83     max_heapify(a, size);
 84     for (int i = size -1; i>0; i--) {
 85         swap(a, 0, i);
 86         tempsize --;
 87         max_heapify(a, tempsize);
 88     }
 89 }
 90 int main () {
 91     
 92     //int a[] = {16,4,10,14};
 93     int a[10000];
 94     for (int i=0; i<10000; i++) {
 95         a[i] = i;
 96     }
 97     int size = sizeof a / sizeof a[0];
 98     suanfa sf(size);
 99     //sf.heapify_sort(a, size);
100     //sf.heapify(a, 2);
101     sf.max_heapify(a, size);
102     for (int i=0; i<size; i++) {
103         cout << a[i] << " ";
104     }
105     cout << endl;
106     return 0;
107 }
108 

posted on 2010-06-01 22:53 幽梦还乡 阅读(228) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理