服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - C/C++ - 堆基本操作实现最大堆

堆基本操作实现最大堆

2021-01-16 13:16C语言程序设计 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;
}

 

延伸 · 阅读

精彩推荐
  • C/C++C++之重载 重定义与重写用法详解

    C++之重载 重定义与重写用法详解

    这篇文章主要介绍了C++之重载 重定义与重写用法详解,本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...

    青山的青6062022-01-04
  • C/C++学习C++编程的必备软件

    学习C++编程的必备软件

    本文给大家分享的是作者在学习使用C++进行编程的时候所用到的一些常用的软件,这里推荐给大家...

    谢恩铭10102021-05-08
  • C/C++c++ 单线程实现同时监听多个端口

    c++ 单线程实现同时监听多个端口

    这篇文章主要介绍了c++ 单线程实现同时监听多个端口的方法,帮助大家更好的理解和学习使用c++,感兴趣的朋友可以了解下...

    源之缘11542021-10-27
  • C/C++C/C++经典实例之模拟计算器示例代码

    C/C++经典实例之模拟计算器示例代码

    最近在看到的一个需求,本以为比较简单,但花了不少时间,所以下面这篇文章主要给大家介绍了关于C/C++经典实例之模拟计算器的相关资料,文中通过示...

    jia150610152021-06-07
  • C/C++C语言实现电脑关机程序

    C语言实现电脑关机程序

    这篇文章主要为大家详细介绍了C语言实现电脑关机程序,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...

    xiaocaidayong8482021-08-20
  • C/C++深入理解goto语句的替代实现方式分析

    深入理解goto语句的替代实现方式分析

    本篇文章是对goto语句的替代实现方式进行了详细的分析介绍,需要的朋友参考下...

    C语言教程网7342020-12-03
  • C/C++详解c语言中的 strcpy和strncpy字符串函数使用

    详解c语言中的 strcpy和strncpy字符串函数使用

    strcpy 和strcnpy函数是字符串复制函数。接下来通过本文给大家介绍c语言中的strcpy和strncpy字符串函数使用,感兴趣的朋友跟随小编要求看看吧...

    spring-go5642021-07-02
  • C/C++C语言中炫酷的文件操作实例详解

    C语言中炫酷的文件操作实例详解

    内存中的数据都是暂时的,当程序结束时,它们都将丢失,为了永久性的保存大量的数据,C语言提供了对文件的操作,这篇文章主要给大家介绍了关于C语言中文件...

    针眼_6702022-01-24