数据结构----二叉堆和优先权队列

堆有序:当一棵二叉树的每个结点都大于等于它的两个子结点时,它被称为堆有序。根结点是堆有序的二叉树中的最大节点。

二叉堆:二叉堆是一组能够用堆有序的完全二叉树排序的元素,并在数组中按层级存储(不使用数组的第一个位置)。

二叉堆可以使用数组或者二叉树实现,在这里使用数组实现。在数组中,根结点放置在下标为1的空间内;下标k的结点的父结点的下标为⌊k⌋,它的两个子结点的下标为2k和2k+1. 

堆的实现:

构造堆的过程中,肯定会用到比较方法和交换方法:

//比较方法
private boolean less(int i,int j)
{ return pq.[i].compareTo(pq[j])<0; }
//交换方法
priivate void exch(int i,intj)
{ Key t = pq[i]; pq[i] = pq[j]; pq[j] = t; }

在对堆进行有序化的过程中会遇到两种情况:

  • 当某个节点优先级上升(或在堆底加入了一个新元素)时,我们需要由下至上恢复堆的顺序;
  • 当某个节点优先级下降(例如将根结点替换为一个较小节点)时,我们需要由上至下恢复堆的顺序;

我们把由下至上恢复堆的顺序称为上浮,把由上至下恢复堆的顺序叫下沉

堆的上浮操作:

private void swim(int k){
    while(k>1 && less(k/2,k){
        exch(k/2,k);
        k=k/2;
    }
}

堆的下沉操作:

private void sink(int k){
    while(2*k <= N){
        int j = 2*k;
        if(j<N && less(j,j+1)) j++;    //保证j是k两个子节点中的较小者
        if(!less(k,j)) break;    //如果k大于j,结束
        exch(k,j);
        k = j;
    }
}

通过使用上面的方法,我们就可以构造出一个堆,堆的插入操作和删除最大元素操作都可以在对数级别的时间内完成。

  • 插入元素:我们将新元素插入数组末尾,增加堆的大小并让新元素上浮到正确位置;
  • 删除最大元素:我们从数组顶端删去最大元素并将数组末尾元素置入顶端,下沉它到正确位置。

优先权队列:

优先权队列的功能就是插入元素和删除最大元素,所以我们完全可以基于堆来实现优先权队列。

明白堆和上面的代码,优先权队列很容易实现,直接来看代码:

public class MaxPQ<Key extends Comparable<Key>>{
    private Key[] pq;    //基于堆
    private int N;    //堆的大小

    public MaxPQ(int maxN)
    { pq = (Key[]) new Comparable[maxN+1]; }

    public void insert(Key v){
        pq[++] = v;
        swim(N);    //恢复堆的有序性
    }
    public Key delMax(){
        public Key max = pq[1];
        exch(1,N--);    //和最后一个节点交换
        pq[N-1] = null;    //防止对象游离
        sink(1);    //恢复堆的有序性
        return max;
}
//less()、exch()、swim()、sink()方法见上文
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Java帮帮-微信公众号-技术文章全总结

HashSet 源码分析【面试+工作】

在工作中,经常有这样的需求,需要判断某个ID是否在某个组的管理之下等,就需要查询该组下的ID放到一个集合中,且集合中元素不能有重复,之后判断该集合是否包含我们的...

1233
来自专栏撸码那些事

【图解数据结构】 线性表

2144
来自专栏coolblog.xyz技术专栏

ArrayList 源码详细分析

ArrayList 是一种变长的集合类,基于定长数组实现。ArrayList 允许空值和重复元素,当往 ArrayList 中添加的元素数量大于其底层数组容量时...

4308
来自专栏JavaEdge

Java中Collections.sort()方法的演变结果分析源码分析关于Java8中Collections.sort方法的修改

4617
来自专栏xingoo, 一个梦想做发明家的程序员

二叉堆

容易证明: 一棵高为h的完全二叉树有2^h 到 2^(h+1)-1个结点。 这就意味着,完全二叉树的高是[logN] 特点: 任意位置i: 左儿子在位置2i上,...

2118
来自专栏自学笔记

Data Structurestackheapheap的实现索引堆tree并查集图 Graph

堆的基本性质: ①堆中的某一个节点总是不小于或不大于其父节点的值。 ②堆总是一棵完全二叉树 比较经典的堆有二叉堆,费波纳茨堆等等。如果一棵二叉树最下层上的...

1013
来自专栏机器学习实践二三事

leetcode之-题19

题目 [图片] Given a linked list, remove the nth node from the end of list and re...

2027
来自专栏mathor

Map

1514
来自专栏大数据钻研

Java 集合框架 ArrayList 源码剖析

总体介绍 ArrayList实现了List接口,是顺序容器,即元素存放的数据与放进去的顺序相同,允许放入null元素,底层通过数组实现。除该类未实现同步外,其余...

35712
来自专栏电光石火

HashSet/HashMap详解

HashMap和HashSet是Java Collection接口两个重要的成员,其中HashMap是Map接口常用的实现类,HashSet是Set接口常用...

23410

扫码关注云+社区

领取腾讯云代金券