程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 堆根本操作完成最年夜堆

堆根本操作完成最年夜堆

編輯:關於C++

堆根本操作完成最年夜堆。本站提示廣大學習愛好者:(堆根本操作完成最年夜堆)文章只能為提供參考,不一定能成為您想要的結果。以下是堆根本操作完成最年夜堆正文



/**
* 完成最年夜堆
*
*/

#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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved