文档章节

初学数据结构--堆和优先队列

loubobooo
 loubobooo
发布于 02/18 15:36
字数 2875
阅读 98
收藏 0

初学数据结构--堆和优先队列

在之前的那两章详细的向各位介绍了二分搜索树这种数据结构,同时我们使用二分搜索树实现了集合映射这两个相对来讲更加高层的数据结构。那么,这种数据结构本身在计算机科学领域占有重要的地位。这种数据结构之所以占有重要的地位,绝不仅仅是因为二分搜索树这样的一种结构,而是树这种形状本身可以产生非常多的拓展。在面对不同问题的时候,我们可以稍微改变或者限制树这种数据结构的性质,从而产生不同的数据结构,高效地解决不同的问题。

在这里我给各位举四个不同的树的例子。它们分别是堆、线段树、字典树以及并查集。那么通过这些不同树的结构学习,可以体会到数据结构的灵活之处,以及我们在设计数据结构的时候其中的一些思考。

优先队列

优先队列本身也是一种队列,对于和普通队列的先进先出的结构有所不同,主要区别在于出队操作上,出队顺序和入队顺序无关,而是跟元素的优先级密切相关。典型的例子:系统中同时执行多个任务,并为多个任务去分配CPU的时间片,此时系统就要看各个任务的优先级,去动态的选择优先级最高的任务去执行。

什么是动态

在这里呢,我简单画了一个示意图,如下图所示:

假设有一个任务处理中心,现在有三个任务请求,而这个任务处理中心可能就需要先要找出这些任务请求中优先级最高的那个请求,相应的进行处理。再处理完这个任务的同时,很有可能又来了很多新的任务请求,这时候要随时根据新来的任务的情况,调整整个队列的优先级,这就是动态。因此任务处理中心并不是一开始就知道所有的任务是什么,排排序就好了。而是随着时间的推移,会不停的有新元素入队,也就是队列中的元素是在不断变化,所以我们必须使用一个优先队列这样的数据结构来解决问题。

优先队列的时间复杂度

针对优先队列这样的一种结构,我们也是可以使用不同的底层实现。

  • 无论是数组还是是链表,都可以直接用这种普通的线性结构充当优先队列的实现方式
  • 也可以使用顺序线性结构。而顺序线性结构是指整个线性结构一直维持所有的元素的顺序。换句话说,整个线性结构一直是从小到大排列或者从大到小排列
  • 甚至我们可以使用堆这种数据结构来实现优先队列。对于入队操作和出队操作,可以做到是O(logn)这个级别的复杂度,而且和之前讲的二分搜索树平均在O(logn)这个级别不同,堆可以在最差的情况下都是O(logn)这个级别。这使得堆这种数据结构是相当高效的。
入队 出队(拿出最大元素)
普通线性结构 O(1) O(n)
顺序线性结构 O(n) O(1)
O(logn) O(logn)

基于堆的优先队列实现

优先队列的代码实现

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {

    private MaxHeap<E> maxHeap;

    public PriorityQueue(){
        maxHeap = new MaxHeap();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    @Override
    public int getSize() {
        return maxHeap.getSize();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }
}

总结

在这一小节,我就简单的介绍了什么是优先队列,并且引出了我们可以使用这种数据结构作为优先队列的底层实现,完成一个高效的优先队列这样的数据结构。

二叉堆

二叉堆的性质

  • 二叉堆是一棵完全二叉树
  • 堆中某个节点的值总是不大于其父节点的值(最大堆),或者是堆堆中某个节点的值总是不小于其父节点的值(最小堆)

二叉堆的种类

  • 最大堆:父结点的键值总是大于或等于任何一个子节点的键值;
  • 最小堆:父结点的键值总是小于或等于任何一个子节点的键值。

二叉堆的构建(Heapify)

构建二叉堆,是把一个无序的完全二叉树调整为二叉堆,本质上就是让所有非叶子节点依次下沉sift down。其算法复杂度则是O(nlogn)。

  • 首先,我们从最后一个非叶子节点开始,也就是从节点22开始。如果节点22小于于它左右孩子中最大的一个,则节点22下沉。
  • 接下来轮到节点13,如果节点13小于它左右孩子中最大的一个,则节点13下沉。
  • 接下来轮到节点19,如果节点19小于它左右孩子中最大的一个,则节点19下沉。
  • 接下来轮到节点17,如果节点17小于它左右孩子中最大的一个,则节点17下沉。
  • 节点15继续比较,继续下沉。
  • 这样一来,一颗无序的完全二叉树就构建成了一个最大堆。

过程如下图所示:

示例代码:

public MaxHeap(E[] arr){
    data = new Array<>(arr);
    // 对最后一个节点的父亲节点 作下沉操作
    for(int i = parent(arr.length -1); i >= 0; i--){
        siftDown(i);
    }
}

二叉堆的插入操作

从堆的角度看,向堆中添加一个元素这个过程,可以称之为sift up(上浮)。

  • 二叉堆的节点插入,插入位置是完全二叉树的最后一个位置。比如我们插入一个新节点,值是 52。
  • 这时候,我们让节点52的父节点16做比较,如果52>16,则让新节点“上浮”,和父节点交换位置。
  • 继续用节点52和父节点41做比较,如果52>41,则让新节点继续“上浮”。
  • 继续比较,最终新节点52<62,此时sift up操作就结束了。

过程如下图所示:

示例代码:

// 筛选(上浮)元素,使满足 堆中某个节点的值总是不大于其父节点的值
private void siftUp(int k){
  // 父节点和子节点做比较,父元素要小的话,交换父子元素
  while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
  data.swap(k, parent(k));
  // 同时替换索引
  k = parent(k);
  }
}

// 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
private int parent(int index){
  if(index == 0){
  throw new IllegalArgumentException("index-0 doesn't have parent");
  }
  return (index - 1) / 2;
}

二叉堆的删除操作

对于堆来说,之所以管它叫做最大堆,是因为每次从堆中取出元素,只取出堆顶的元素,也就是这棵二叉树的根节点所在的这个元素

  • 二叉堆的节点删除过程和插入过程正好相反,所删除的是处于堆顶的节点。比如我们删除最大堆的堆顶节点62。
  • 这时候,为了维持完全二叉树的结构,我们把堆的最后一个节点16补到原本堆顶的位置。
  • 接下来我们让移动到堆顶的节点16和它左右孩子进行比较,如果左右孩子中最大的一个(显然是左节点52)比节点16大,那么让节点16“下沉”。
  • 继续让节点16和它的左右孩子做比较,左右孩子中最大的是节点41,由于16<41,让节点16继续“下沉”。
  • 继续让节点16和它的左右孩子做比较,此时满足最大堆的性质,结束sift down操作。
  • 这样一来,二叉堆重新得到了调整。

过程如下图所示:

示例代码:

// 筛选(下沉)元素,使满足 堆中某个节点的值总是不大于其父节点的值
private void siftDown(int k){
  // k节点所在的索引 比 data的总数还要小
  while(leftChild(k) < data.getSize()){
    int j = leftChild(k);

    // 判断有右孩子,并且比较左右孩子的大小
    if(j + 1 < data.getSize() &&
       data.get(j + 1).compareTo(data.get(j)) > 0){
      j = rightChild(k);
      // data[j] 是leftChild和rightChild中的最大值
    }
    // k是头节点比左右孩子都要大即可中断
    if(data.get(k).compareTo(data.get(j)) >= 0){
      break;
    }
    data.swap(k ,j);
    k = j;
  }
}

最大堆的代码实现

public class MaxHeap<E extends Comparable<E>> {

    private Array<E> data;

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

    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);
        }
    }

    // 返回堆中的元素个数
    public int getSize(){
        return data.getSize();
    }

    // 返回一个布尔值,表示堆中是否为空
    public boolean isEmpty(){
        return data.isEmpty();
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的父亲节点的索引
    private int parent(int index){
        if(index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent");
        }
        return (index - 1) / 2;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的左孩子节点的 索引
    private int leftChild(int index){
        return index * 2 + 1;
    }

    // 返回完全二叉树的数组表示中,一个索引所表示的元素的右孩子节点的 索引
    private int rightChild(int index){
        return index * 2 + 2;
    }

    // 向堆中添加元素
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    // 筛选(上浮)元素,使满足 堆中某个节点的值总是不大于其父节点的值
    private void siftUp(int k){
        // 父节点和子节点做比较,父元素要小的话,交换父子元素
        while(k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k, parent(k));
            // 同时替换索引
            k = parent(k);
        }
    }

    // 看堆中最大元素
    public E findMax(){
        if(data.getSize() == 0){
            throw new IllegalArgumentException("Can not findMax when heap is empty.");
        }
        return data.get(0);
    }

    // 取出堆中最大元素
    public E extractMax(){
        E ret = findMax();

        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);

        return ret;
    }

    private void siftDown(int k){
        // k节点所在的索引 比 data的总数还要小
        while(leftChild(k) < data.getSize()){
            int j = leftChild(k);

            // 判断有右孩子,并且比较左右孩子的大小
            if(j + 1 < data.getSize() &&
                    data.get(j + 1).compareTo(data.get(j)) > 0){
                j = rightChild(k);
                // data[j] 是leftChild和rightChild中的最大值
            }
            // k是头节点比左右孩子都要大即可中断
            if(data.get(k).compareTo(data.get(j)) >= 0){
                break;
            }
            data.swap(k ,j);
            k = j;
        }
    }
}

总结

在这一章从一个更广义的角度来理解了优先队列,并拓展了优先队列的定义。比如普通队列的先到先得,优先队列(拿出优先级最高的那个元素作为出队的元素)这样的队列。

© 著作权归作者所有

loubobooo

loubobooo

粉丝 15
博文 75
码字总数 90684
作品 0
杭州
程序员
私信 提问
加载中

评论(0)

【算法与数据结构】二叉堆和优先队列 Priority Queue

优先队列的特点 普通队列遵守先进先出(FIFO)的规则,而优先队列虽然也叫队列,规则有所不同: 最大优先队列:优先级最高的元素先出队 最小优先队列:优先级最低的元素先出队 优先队列可以用...

kikajack
03/31
0
0
数据结构与算法(4)——优先队列和堆

前言:题图无关,接下来开始简单学习学习优先队列和堆的相关数据结构的知识; 前序文章: 数据结构与算法(1)——数组与链表(https://www.jianshu.com/p/7b93b3570875) 数据结构与算法(2)—...

我没有三颗心脏
2018/07/12
0
0
关于PriorityQueue 二叉堆的问题

场景:最近在研究java中的队列,当研究到优先队列的时候去读 PriorityQueue的源码的时候发现一种数据结构,我数据结构这块基本上上是空白,所以让我晦涩难懂啊,于是我查阅了大量资料以及手动...

skyline520
2013/06/01
931
0
【从蛋壳到满天飞】JS 数据结构解析和算法实现-堆和优先队列(一)

前言 【从蛋壳到满天飞】JS 数据结构解析和算法实现,全部文章大概的内容如下: Arrays(数组)、Stacks(栈)、Queues(队列)、LinkedList(链表)、Recursion(递归思想)、BinarySearchTree(二分搜...

哎哟迪奥
2019/03/26
0
0
二叉堆与优先队列

一、优先队列 1.简单介绍 优先队列是一种抽象的数据结构,它与我们生活中的许多场景息息相关。比如我们的电脑或者手机,很多时候我们后台会运行多个程序,当程序过多导致内存急剧减少时,如果...

丶legend
2017/10/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

RabbitMQ消息中间件技术精讲笔记

[TOC] RabbitMQ消息中间件技术精讲笔记 错别字有点多, 改了一部分. 剩下的不影响阅读,实在没精力改了... 业界主流消息中间件介绍 MQ衡量指标 服务性能 数据存储 集群架构 主流MQ介绍 Active...

我爱吃炒鸡
昨天
11
0
从"曼巴精神"中学到的做事方式

致敬曼巴 最近一直想写一篇关于曼巴精神的文章,作为科比球迷,今年发生的事情的确让我们难过,不过生活还要继续,虽然科比已经离开了我们,但曼巴精神永存,下面从几点来讲述曼巴精神在我们...

科比可比克
昨天
23
0
使用JavaScript在文本框中的Enter键上触发按钮单击

问题: I have one text input and one button (see below). 我有一个文本输入和一个按钮(见下文)。 How can I use JavaScript to trigger the button's click event when the Enter key ......

技术盛宴
昨天
23
0
展示如何在checkout里使用quote,quote item, address, shopping cart

展示如何更改并且在定制化的时候高效应用这些模块。 以下实体继承 \Magento\Framework\Model\AbstractExtensibleModel ,所以你可以使用第4章中讨论的可扩展属性。 Quote Quotes 是客户购物车...

忙碌的小蜜蜂
昨天
18
0
面向对象思想设计原则及常见设计模式

1、面向对象思想设计原则 在实际的开发中,我们要想更深入的了解面向对象思想,就必须熟悉前人总结过的面向对象的思想的设计原则 1.1、单一职责原则 高内聚,低耦合 每个类应该只有一个职责,...

庭前云落
昨天
31
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部