欧美久久久久久久,九色在线视频,一级欧美

復(fù)制代碼代碼如下:

/**
* 實(shí)現(xiàn)最大堆
*
*/

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

using namespace std;
const int M = 10003;

//定義數(shù)據(jù)節(jié)點(diǎn)
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;
//數(shù)組下標(biāo)從0開(kāi)始
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;
}
//對(duì)數(shù)組h建立成堆
void build();
//插入一個(gè)元素
void insert(T data);
//彈出堆頂元素
void pop(){
  h[0] = h[--n];
  heapify(0);
};
//堆頂元素
T top(){return h[0];}
//打印數(shù)組中的全部元素
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);
}
}
/**
* 插入的過(guò)程就是將data放到數(shù)組下標(biāo)為n的
* 那里，也就是數(shù)組的最后一個(gè)的元素后面
*
* 插入之后需要做的就是做保持堆性質(zhì)的工作，這個(gè)非常簡(jiǎn)單
* 因?yàn)樗龅墓ぷ骶褪菍⑿略龅膁ata放到一條【有序鏈】上的合適位置（放入data后依然有序）
* 這條有序鏈就是【data的上一個(gè)元素】到root之間的一條鏈，這條鏈絕對(duì)是有序的
* 你就完全將這條鏈當(dāng)做是一個(gè)數(shù)組（只是上一個(gè)元素的下標(biāo)不是減一）
* 假如需要放的位置是m，那么就將m ———— (n - 1)的元素全部向下移動(dòng)，然后將鏈尾被
* 擠出來(lái)的data放到位置m那里就好了
*/

template<class T>
void Heap<T>::insert(T data){
h[n++] = data;
T tmp = data;  //將新增的節(jié)點(diǎn)保存
int cur = n - 1; //當(dāng)前節(jié)點(diǎn)，由于之前n++過(guò)了,所以減一
//循環(huán)找到合適放tmp的位置，并不斷向后移動(dòng)元素給待放的tmp騰出位置
while(cur > 0 && h[P(cur)] < tmp){  //當(dāng)tmp比cur的父親大的時(shí)候
  h[cur] = h[P(cur)];
  cur = P(cur);
}
//現(xiàn)在的cur位置就是合適放tmp的位置了
h[cur] = tmp;
}
/**
* 調(diào)整cur這棵樹(shù)滿足堆（最大堆）
* 從cur的兩個(gè)孩子中找到最大值A(chǔ)和cur交換
* 然后從剛才最大值A(chǔ)中那個(gè)節(jié)點(diǎn)的位置遞歸調(diào)整（向下調(diào)整）
*/

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();