• 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html
  • 极客专栏正式上线!欢迎访问 https://www.jikewenku.com/topic.html

数据结构笔记总结(7.5)Heapify和Replace

极客笔记 Geekerstar 11个月前 (05-19) 490次浏览 已收录 0个评论 扫描二维码
文章目录[隐藏]

Replace

取出最大元素后,放入一个新的元素。

  • 实现:可以先extraMax,再add,两次O(logn)的操作
  • 实现:可以直接将堆顶元素替换以后Sift Down,一次O(logn)的操作

代码演示

// 取出堆中的最大元素,并且替换成元素e
public E replace(E e){
    E ret = findMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

Heapify

将任意数组整理成堆的形状。将当前数组看成一个完全二叉树,这个例子中,对于这个数组并不是一个堆,不满足堆的性质。

但是我们同样可以把它看成一棵完全二叉树,对于这个完全二叉树,我们从最后一个非叶子节点开始计算,如下图所示有五个叶子节点:

最后一个非叶子节点就是22这个元素所在的节点,从这个节点开始倒着从后向前不断的Sift Down就可以了。

首先由一个非常重要的问题,就是我们如何定位最后一个非叶子节点所处的索引是多少?

其实我们只需要拿到最后一个节点的索引,然后根据这个索引计算它的父节点的索引是谁就好了。

程序中只需要调用parent(最后一个节点的索引),最后一个节点的索引非常好求,从0开始整个size-1,父亲节点的索引index-1再除以2。接下来就进行Sift Down操作,22和62交换,此时22已经是叶子节点了,下沉操作就完成了。

然后看索引为3的节点,13和41交换,13变成叶子节点无法继续下沉。

然后接下来依次类推,最终结果如下,建议仔细分析一下操作流程。

Heapify的算法复杂度

将n个元素逐个插入到一个空堆中,算法复杂度是O(nlogn)
使用Heapify的过程,算法复杂度为O(n)

代码演示

public MaxHeap(){
    data = new Array<>();
}

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    for(int i = parent(arr.length - 1) ; i >= 0 ; i --)
        siftDown(i);
}

在Array.java中添加一个新的构造函数

public Array(E[] arr){
    data = (E[])new Object[arr.length];
    for(int i = 0 ; i < arr.length ; i ++)
        data[i] = arr[i];
    size = arr.length;
}

Main.java中编写一个测试函数

private static double testHeap(Integer[] testData, boolean isHeapify){

    long startTime = System.nanoTime();

    MaxHeap<Integer> maxHeap;
    if(isHeapify)
        maxHeap = new MaxHeap<>(testData);
    else{
        maxHeap = new MaxHeap<>();
        for(int num: testData)
            maxHeap.add(num);
    }

    int[] arr = new int[testData.length];
    for(int i = 0 ; i < testData.length ; i ++)
        arr[i] = maxHeap.extractMax();

    for(int i = 1 ; i < testData.length ; i ++)
        if(arr[i-1] < arr[i])
            throw new IllegalArgumentException("Error");
    System.out.println("Test MaxHeap completed.");

    long endTime = System.nanoTime();

    return (endTime - startTime) / 1000000000.0;
}

下面测试一下,还是用上一节的测试用例

public static void main(String[] args) {

    int n = 1000000;

    Random random = new Random();
    Integer[] testData = new Integer[n];
    for(int i = 0 ; i < n ; i ++)
        testData[i] = random.nextInt(Integer.MAX_VALUE);

    double time1 = testHeap(testData, false);
    System.out.println("Without heapify: " + time1 + " s");

    double time2 = testHeap(testData, true);
    System.out.println("With heapify: " + time2 + " s");
}

最终的运行结果如下

在我的电脑上,对于一百万的数据量,如果不使用Heapify操作的话时间是2.17秒,如果使用Heapify的话时间是1.25秒。

源码下载

下载地址

导航目录

查看导航
丨极客文库, 版权所有丨如未注明 , 均为原创丨
本网站采用知识共享署名-非商业性使用-相同方式共享 3.0 中国大陆许可协议进行授权
转载请注明原文链接:数据结构笔记总结(7.5)Heapify和Replace
喜欢 (0)
[247507792@qq.com]
分享 (0)
Geekerstar
关于作者:
本站技术支持

您必须 登录 才能发表评论!

  • 精品技术教程
  • 编程资源分享
  • 问答交流社区
  • 极客文库知识库

客服QQ


QQ:2248886839


工作时间:09:00-23:00