小根堆的Java实现

1. 堆

堆是完全二叉树的数组形式,由于堆没有指针指向,所以可以利用下标来模拟指向,假设 i 为父节点,那么 2i+1 为左孩子,2i+2 为右孩子。假设 i 为当前节点,那么 (i - 1) / 2 为父节点

根据大小排序可分为小根堆和大根堆,小根堆即元素越小越在上方,大根堆则相反。这里注意:元素大小并不是按数组下标来排序的,下图的数字对应数组的坐标

堆的应用:

  • 堆排序
  • 优先级队列
  • 快速找最值

2. 小根堆实现

内部操作有:

  • 上浮:将小的元素往上移动、当插入元素时,将元素插入末尾,这样上移即可调整位置
  • 下沉:将大的元素向下移动、当删除元素时,将首位交换,弹出尾部,首部下移即可调整位置
  • 插入:添加元素
  • 弹出:删除元素

主要是其插入弹出的思想,还有调整时注意下标,因为大小与下标相差1

package heap;

// 小根堆时间复杂度是O(1) ~ O(logn)
// 默认O(nlogn)
public class Heap {

    // 实际存放元素个数
    // 这里是个坑,debug了好久,起因:下标 = 实际大小-1
    private int size;

    // 数组存储元素
    // 可以实现简单扩容,size++ > capacity时
    // data = copyOf(data,capacity*2);
    private int[] data = new int[10];

    // 交换,传入下标
    private void swap(int a, int b) {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;
    }

    // 较大的下沉
    // 将当前节点与其较小儿子交换
    // 并将更新当前节点为交换的儿子节点
    public void fixDown(int index) {
        int son = index * 2 + 1;
        while (son <= size) {
            if (son + 1 < size && data[son + 1] < data[son]) {
                son++;  // 这里这要比较左右孩子谁小
            }
            if (data[index] < data[son]) {
                break;  // 当前节点比孩子节点小,不用下沉退出循环
            } else {
                swap(index, son);
                index = son;
                son = index * 2 + 1;
            }
        }
    }

    // 较小的上浮
    // 当前节点与父节点相比,若小于则交换,且将当前节点跟新为其父节点
    public void fixUp(int index) {
        int father = (index - 1) / 2;
        while (father >= 0) {
            // 这里卡死一次,debug后发现,只有一个元素会相等进入无限交换
            if (data[index] >= data[father]) {
                break;  // 其父节点大于当前节点,不用上浮退出循环
            } else {
                swap(index, father);
                index = father;
                father = (index - 1) / 2;
            }
        }
    }

    // 插入
    // 每次都在最后一个插入,然后上浮到合适位置
    public Heap push(int value) {
        data[size] = value;
        fixUp(size++);
        return this;
    }

    // 弹出根元素
    // 让根元素和尾元素交换,让现在的根元素下沉即可
    public int pop() {
        swap(0, --size);
        fixDown(0);
        return data[size];
    }

    // 测试
    public static void main(String[] args) {
        Heap heap = new Heap();

        // 乱序添加1~9
        // 从输出也可以验证,元素大小并不是按数组小标来排序的
        // 输出:123459786
        heap.push(8).push(5).push(9)
                .push(4).push(2).push(3)
                .push(6).push(7).push(1);
        while(heap.size > 0){
            System.out.print(heap.pop());
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数组

    数组是一个相同类型的变量的集合,注意数组是长度固定的,而且本身也属于引用类型 之前说过字符串和数组经常使用,所以这里先讲一下下字符串和字符数组互转

    晚上没宵夜
  • 剑指Offer-2

    晚上没宵夜
  • Java的标签

    以前笔者如何退出双重循环呢? 利用循环条件判断,加上break、continue、return可以改变流程

    晚上没宵夜
  • 算法不想学(二): 堆排序和top k

    sean_yang
  • Leetcode 132 Palindrome Partitioning II

    Given a string s, partition s such that every substring of the partition is a p...

    triplebee
  • BZOJ2783: [JLOI2012]树(树上前缀和+set)

    Description 数列 提交文件:sequence.pas/c/cpp 输入文件:sequence.in 输出文件:sequence.out 问题描述:...

    attack
  • 《一文说透数据结构》系列之什么是堆?看这一篇就够了

    本文将首先介绍什么是堆,然后介绍了堆的插入和删除操作,最后给出了堆的代码实现,并进行了测试。

    乔戈里
  • 浅谈我对动态规划的一点理解---大家准备好小板凳,我要开始吹牛皮了~~~

    前言 作为一个退役狗跟大家扯这些东西,感觉确实有点。。。但是,针对网上没有一篇文章能够很详细的把动态规划问题说明的很清楚,我决定还是拿出我的全部家当,来跟大家分...

    Angel_Kitty
  • L2-006. 树的遍历

    给定一棵二叉树的后序遍历和中序遍历,请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

    指点
  • c++之数组

    绝命生

扫码关注云+社区

领取腾讯云代金券