首页
登录 | 注册

索引堆

索引堆:

分为任意类型的数据域 和 整数类型的索引域

可以快速改变已构建好的堆中的元素的值,可以快速交换堆中的元素,普通堆很难做到

 

主要思想是给每个 原始数据 都 标一个不同的号,相当于把数据压缩,建堆、操作堆时,被操作的只是索引,数据的交换被省略,但

由于索引代表了数据,所以依然可以将 原始数据 建立成“逻辑堆”。

好处:建堆时的“数据交换”的时间用空间代替了,如果每个单位数据都是一颗 决策树 ,那么时间的消耗只会集中在“数据比较”上,

数据交换的时间消耗被降低了(想一下交换一颗树简单还是交换一个数简单)。

弊处:由于额外要开一个index数组,空间消耗上增大了

 

 

 以C++ 中 的string类型作为数据域,来写一个例子,(chenge函数懒得写)

/*

输入n个字符串,按照字典序进行排序,

并输出,一行一个

*/

 

以下是代码实现

#include<iostream>
#include<string>
using namespace std;
class IndexHeap{
    private:
        string data[1010];
        int index[1010];
        int heap_Size;
    public:
        int get();//取出堆顶元素 的 index(索引)
        void put(string x);//在堆中插入一个元素 
        void start(int n);//初始化index数组 
        void heapsort();//输出
}a;

void IndexHeap::put(string x) {
    heap_Size++;
    data[heap_Size] = x;
    int now = heap_Size,next;
    
    while(now > 1) {
        next = now/2;
        if(data[index[next]] >= data[index[now]]) break;
        swap(index[next],index[now]);
        now = next;
    }
    
    return;
} 

void IndexHeap::start(int n) {
    for(int i = 1; i <= n; ++i) index[i] = i;
    string m;
    for(int i = 1; i <= n; ++i) {
        cin>>m;
        put(m);
    }
}

int IndexHeap::get() {
    int res = index[1];
    index[1] = index[heap_Size--];
    int now = 1,next;
    while(now*2 <= heap_Size) {
        next = now * 2;
        if(next < heap_Size && data[index[next + 1]] > data[index[next]]) next++;
        if(data[index[now]] >= data[index[next]]) break;
        swap(index[now],index[next]);
        now = next;
    }
    return res;
}

void IndexHeap::heapsort() {
    int k = heap_Size;
    for(int i = 1; i < k; ++i) {
        int m = heap_Size;
        index[m] = get();
    }
    for(int i = 1; i <= k; ++i)
        cout<<data[index[i]]<<'\n';
    return;
}


int main() {
    int n;
    cin>>n;
    a.start(n);
    a.heapsort();
    return 0;
}

 


相关文章

  • Linux的内存分页管理
    作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁转载   内存是计算机的主存储器.内存为进程开辟出进程空间,让进程在其中保存数据.我将从内存的物理特性出发,深入到内存管理的细节,特别是了解虚拟内存和内存 ...
  • More Effective C++
    More Effective C++ 35个改善编程与设计的有效方法 只有深入了解C++编译器如何解释代码, 才有可能用C++语言写出健壮的软件. C++的难学, 不仅在其广博的语法, 语法背后的语义, 语义背后的深层思维, 深层思维背后的 ...
  • 学了很多乱七杂八的东西,但是依然停留在前端,在工作中一直和后端交流,但是不太了解数据库是怎么回事,为了加强学习,准备学习一些关于数据库相关的东西. 说起数据库可能会有很多很多,SQLServer.Oracle.Sybase等等等,还有就是要 ...
  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • 为什么说 Java 程序员到了必须掌握 Spring Boot 的时候?
    Spring Boot 2.0 的推出又激起了一阵学习 Spring Boot 热,就单从我个人的博客的访问量大幅增加就可以感受到大家对学习 Spring Boot 的热情,那么在这么多人热衷于学习 Spring Boot 之时,我自己也在 ...
  • WebGL three.js学习笔记 法向量网格材质MeshNormalMaterial的介绍和创建360度全景天空盒的方法
    WebGL学习----Three.js学习笔记(5) 点击查看demo演示 Demo地址:https://nsytsqdtn.github.io/demo/360/360 简单网格材质 MeshNormalMaterial MeshNorm ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.077 s.
京ICP备10005923号