堆基本操作实现最大堆

/**
* 实现最大堆
*
*/


#include <iostream> #include <cstring> #include <string> #include <algorithm> #include <cstdio>

using namespace std; const int M = 10003;

//定义数据节点 class dNode{ public:  string name;  int age;  double score;  dNode():name("no name"), age(0), score(0.0){}  dNode(string name, int age, double score):name(name), age(age), score(score){}  bool operator < (const dNode & d){   return score < d.score;  }  bool operator > (const dNode &d){   return score > d.score;  }  bool operator = (const dNode &d){   name = d.name;age=d.age;score=d.score;  }  bool operator == (const dNode &d){   return name == d.name && age == d.age && score == d.score;  }  void swap(dNode & a, dNode & b){   dNode tmp = a;   a = b;   b = tmp;  }  void show(){   cout << "***************" << endl;   cout << "name: " << name << endl;   cout << "age: " << age << endl;   cout << "score: " << score << endl;  } }; //定义堆 template<class T> class Heap{ public:  dNode h[M];  void heapify(int cur);  int n;  //数组下标从0开始  int L(int i){return (i << 1) + 1;}  int R(int i){return (i << 1) + 2;}  int P(int i){return (i - 1) >> 1;} public:  Heap():n(0){}  Heap(T data[], int len){   memcpy(h, data, sizeof(T) * len);   n = len;  }  //对数组h建立成堆  void build();  //插入一个元素  void insert(T data);  //弹出堆顶元素  void pop(){   h[0] = h[--n];   heapify(0);  };  //堆顶元素  T top(){return h[0];}  //打印数组中的全部元素  void show(){   for(int i = 0; i < n; i++){    cout << "***************" << endl;    cout << "cur: " << i << endl;    cout << "name: " << h[i].name << endl;    cout << "age: " << h[i].age << endl;    cout << "score: " << h[i].score << endl;   }  }

};

template<class T> void Heap<T>::build(){  for(int i = (n / 2) - 1; i >= 0; i--){   heapify(i);  } } /** * 插入的过程就是将data放到数组下标为n的 * 那里，也就是数组的最后一个的元素后面 *   * 插入之后需要做的就是做保持堆性质的工作，这个非常简单 * 因为所做的工作就是将新增的data放到一条【有序链】上的合适位置（放入data后依然有序） * 这条有序链就是【data的上一个元素】到root之间的一条链，这条链绝对是有序的 * 你就完全将这条链当做是一个数组（只是上一个元素的下标不是减一） * 假如需要放的位置是m， 那么就将m ———— (n - 1)的元素全部向下移动，然后将链尾被 * 挤出来的data放到位置m那里就好了 */

template<class T> void Heap<T>::insert(T data){  h[n++] = data;  T tmp = data;  //将新增的节点保存  int cur = n - 1; //当前节点，由于之前n++过了,所以减一  //循环找到合适放tmp的位置，并不断向后移动元素给待放的tmp腾出位置  while(cur > 0 && h[P(cur)] < tmp){  //当tmp比cur的父亲大的时候   h[cur] = h[P(cur)];   cur = P(cur);  }  //现在的cur位置就是合适放tmp的位置了  h[cur] = tmp; } /** * 调整cur这棵树满足堆（最大堆） * 从cur的两个孩子中找到最大值A和cur交换 * 然后从刚才最大值A中那个节点的位置递归调整（向下调整） */

template<class T> void Heap<T>::heapify(int cur){  T mmax = h[L(cur)] > h[R(cur)] ? h[L(cur)] : h[R(cur)];  if(mmax < h[cur])   return;  //cout << "##########" << endl;  //mmax.show();  if(h[L(cur)] == mmax){   h[0].swap(h[cur], h[L(cur)]);   heapify(L(cur));   }else{   h[0].swap(h[cur], h[R(cur)]);   heapify(R(cur));  }  //cout << "##########" << endl;

}

int main(){  int num = 7;  dNode d[M];  for(int i = 0; i < num; i++){   d[i] = dNode("Luo", rand() % 50, rand() % 11);  }  d[0].score = 10;  d[1].score = 33;  d[2].score = 22;  d[3].score = 43;  d[4].score = 7;  d[5].score = 66;  d[6].score = 1;  Heap<dNode> *h = new Heap<dNode>(d, num);  h->build();  h->insert(d[1]);  h->insert(d[3]);  h->show();  cout << "########### test top and pop ####" << endl;  h->top().show();  h->pop();  h->top().show();

 return 0; }