欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

堆和优先队列

程序员文章站 2024-02-15 21:47:52
...

什么是优先队列

堆和优先队列

为什么会使用优先队列

动态:

任务处理中心随时都在处理各种各样的请求,也就是说不是一开始就确定了各种请求的优先级的,请求的优先级是不断地变化的。
堆和优先队列
堆和优先队列
堆和优先队列

堆的基本结构

堆其实也是一棵树。
堆和优先队列

二叉堆的性质 :

首先是一个完全二叉树

堆中某个节点的值总是不大于其父节点的值 ---->最大堆
堆和优先队列

数组实现最大堆

package MaxHeap;

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 int size() {
        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;
    }
}