堆基本操作实现最大堆

代码如下:

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

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

(0)

相关推荐

  • 堆基本操作实现最大堆

    复制代码 代码如下: /*** 实现最大堆**/ #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; dNo

  • C语言实现基于最大堆和最小堆的堆排序算法示例

    堆定义 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质: Key[i]<=key[2i+1]&&Key[i]<=key[2i+2](小顶堆)或者:Key[i]>=Key[2i+1]&&key>=key[2i+2](大顶堆) 即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字. 堆排序的思想 利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性,使得每次从无序中选择最大记录(最小记录)变得简单. 最大堆:所有节点的子节点比其

  • 解读堆排序算法及用C++实现基于最大堆的堆排序示例

    1.堆排序定义 n个关键字序列Kl,K2,-,Kn称为堆,当且仅当该序列满足如下性质(简称为堆性质): (1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤   ) 若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构,则堆实质上是满足如下性质的完全二叉树:树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字. [例]关键字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分别满足堆性质(1

  • java数据结构-堆实现优先队列

    目录 一.二叉树的顺序存储 1.堆的存储方式 2.下标关系 二.堆(heap) 1.概念 2.大/小 根堆 2.1小根堆 2.2大根堆 3.建堆操作 3.1向下调整 4.入队操作 4.1向上调整 4.2push 入队的完整代码展示 5.出队操作 5.1pop 出队代码完全展示 6.查看堆顶元素 7.TOK 问题 7.1TOPK 8.堆排序 文章内容介绍大纲 一.二叉树的顺序存储 1.堆的存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完

  • Java数据结构之优先级队列(堆)图文详解

    目录 一.堆的概念 二.向下调整 1.建初堆 2.建堆 三.优先级队列 1.什么是优先队列? 2.入队列 3.出队列 4.返回队首元素 5.堆的其他TopK问题 总结: 总结 一.堆的概念 堆的定义:n个元素的序列{k1 , k2 , … , kn}称之为堆,当且仅当满足以下条件时: (1)ki >= k2i 且 ki >= k(2i+1) ——大根堆 (2) ki <= k2i 且 ki <= k(2i+1) ——小根堆 简单来说: 堆是具有以下性质的完全二叉树:(1)每个结点的

  • Java深入了解数据结构之优先级队列(堆)

    目录 一,二叉树的顺序存储 ①存储方式 ②下标关系 ③二叉树顺序遍历 二,堆 ①概念 ②操作-向下调整 ③建堆(建大堆为例) 三,堆的应用-优先级队列 ①概念 ②内部原理 ③入队列 ④出队列(优先级最高) ⑤返回队首元素(优先级最高) 四,堆排序 一,二叉树的顺序存储 ①存储方式 使用数组保存二叉树结构,方式即将二叉树用层序遍历方式放入数组中. 一般只适合表示完全二叉树,因为非完全二叉树会有空间的浪费. 这种方式的主要用法就是堆的表示. ②下标关系 已知双亲(parent)的下标,则: 左孩子(

  • c++深入浅出讲解堆排序和堆

    目录 堆是什么 最大堆 最小堆 堆排序 最终代码 关于堆 堆是什么 堆是一种特殊的完全二叉树 如果你是初学者,你的表情一定是这样的

  • C++数据结构之堆详解

    目录 堆的概念 提示:完全二叉树 堆的性质 最大堆最小堆 代码 定义 有限数组形式 动态数组形式 操作 向下调整结点 建立堆 初始化 打印堆 测试 main函数 结果 完整代码 堆的概念 堆(heap)是计算机科学中一类特殊的数据结构的统称.堆通常是一个可以被看做一棵树的数组对象,即是一种顺序储存结构的完全二叉树. 提示:完全二叉树 完全二叉树:对一棵深度为k.有n个结点二叉树编号后,各节点的编号与深度为k的满二叉树相同位置的结点的编号相同,这颗二叉树就被称为完全二叉树.[2] 堆的性质 堆中某

  • C语言数据结构之堆、堆排序的分析及实现

    目录 1.堆的概念结构及分类 1.2堆的分类 1.2.1 大堆 1.2.2 小堆 2. 堆的主要接口 3.堆的实现 3.1 堆的初始化 HeapInit 3.2 堆的销毁 HeapDestory 3.3 堆的打印 HeapPrint 3.4 堆的插入元素 HeapPush   * 3.5 堆的删除元素 HeapPop  * 4.堆的应用:堆排序   *** 4.1 堆排序实现过程分析 4.3 堆排序结果演示 5.堆(小堆)的完整代码 总结  1.堆的概念结构及分类 以上这段概念描述看起来十分复杂

  • Java堆&优先级队列示例讲解(上)

    目录 1. 二叉树的顺序存储 1.1 存储方式 1.2 下标关系 2. 堆(heap) 2.1 概念 2.2 操作-(下沉&上浮)本例是最大堆 2.3 建堆-完整代码(最大堆) 3. 优先级队列 1. 二叉树的顺序存储 1.1 存储方式 使用数组保存二叉树结构,方式即将二叉树用 层序遍历 方式放入数组中. 一般只适合表示完全二叉树,这种方式的主要用法就是堆的表示. 因为非完全二叉树会有空间的浪费(所有非完全二叉树用链式存储). 1.2 下标关系 已知双亲 (parent) 的下标,则: 左孩子

随机推荐