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

java实现最大堆

程序员文章站 2024-02-13 14:04:34
...

优先队列

普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有*先出 (first in, largest out)的行为特征。通常采用堆数据结构来实现。

​ 堆(英语:heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质:

  • 堆中某个节点的值总是不大于或不小于其父节点的值;
  • 堆总是一棵完全二叉树。

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。

将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。

我们这里讲的是二叉堆。

堆的入队和出队的时间复杂度都是O(log n)

java实现最大堆
上图就是一个最大堆的事例

下面我们使用数组来构建一个最大堆,在这里为了便于理解,数组索引为0的节点不存放数值,从第二个节点开始存放数据。

java实现最大堆

当前节点的父节点、左孩子、右孩子的索引就会有如下的关系:

  • 父节点的索引:index/2 (index为当前节点的索引)
  • 左孩子的索引:index*2
  • 右孩子的索引:index*2+1

如果从数组的第一个节点开始存放数据的话,当前节点的父节点、左孩子、右孩子的索引就会有如下的关系:

  • 父节点的索引:(index-1)/2 (index为当前节点的索引)

  • 左孩子的索引:index*2+1

  • 右孩子的索引:index*2+2

最大堆的基础架构
import java.util.ArrayList;
public class MaxHeap<E extends Comparable<E>> {

    //这里使用数组来实现
    private ArrayList<E> data;

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

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

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

    //判断堆是否为空
    public boolean isEmpty() {
        return data.isEmpty();
    }

    //返回完全二叉树中索引为index的节点的父节点的索引
    private int parent(int index) {
        if (index == 0)
            throw new IllegalArgumentException("index-0 doesn't have parent");

        return (index - 1) / 2;
    }

    //返回完全二叉树中索引为index的节点的左孩子的索引
    private int leftChild(int index) {
        return index * 2 + 1;
    }

    //返回完全二叉树中索引为index的节点的右孩子的索引
    private int rightChild(int index) {
        return index * 2 + 2;
    }

    //交换索引为i、j的值
    private void swap(int i, int j) {
        E t = data.get(i);
        data.set(i, data.get(j));
        data.set(j, t);
    }
}
往堆中添加元素
  • 再向堆中添加元素时,除了要维持完全二叉树的结构,还要注意堆的约束条件:根节点的值要大于左右子树的值。

在这里因为我们使用数组来实现的堆,所以添加元素时,我们可以先将元素添加到数组的末尾,然后循环的与父节点比较大小,比父节点大就与父节点交换位置,之后就继续与新的父节点比较大小,直到小于等于父节点。

java实现最大堆

  • 如上图所示,我们要在这个堆中添加一个元素36

java实现最大堆

  • 先将元素添加到数组的末尾。

java实现最大堆

  • 然后通过当前的索引计算出父节点的索引,通过索引得到父节点的值16,通过比较新添加的节点比其父节点大,所以将新添加的值与父节点交换在数组中的位置。之后再与新的父节点41比较,36<41,结束操作。
添加元素的代码实现
//向堆中添加元素
public void add(E e) {
    data.add(e);
    siftUp(data.size() - 1);
}

private void siftUp(int k) {
    //k不能是根节点,并且k的值要比父节点的值大
    while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
        swap(k, parent(k));

        k = parent(k);
    }
}
删除堆顶元素

删除堆顶元素要注意维持堆的特殊性质。这里举个例子。

java实现最大堆

  • 要将这个堆中删除最大值,也就是堆顶元素62,先将62取出。

java实现最大堆

  • 将堆顶元素和堆的最后一个元素互换,也就是数组的首尾元素互换。

java实现最大堆

  • 删除最后一个元素,也就是堆中的最大值

java实现最大堆

  • 将当前的堆顶元素16的左右孩子41、30进行比较,找出最大的一个41,再与根节点16进行比较,左孩子41比根节点16大,所以将根节点与其左孩子互换,如上图所示。
  • 重复上面的操作,直到当前节点的值大于其左右子树。过程如下所示。

java实现最大堆

java实现最大堆

删除堆顶元素的代码实现
//看堆中最大的元素
public E findMax() {
    if (data.size() == 0)
        throw new IllegalArgumentException("Can not findMax when heap is empty");
    return data.get(0);
}

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

    swap(0, data.size() - 1);
    data.remove(data.size() - 1);
    siftDown(0);

    return ret;
}

private void siftDown(int k) {
    //leftChild存在
    while (leftChild(k) < data.size()) {
        int j = leftChild(k);
        //rightChild存在,且值大于leftChild的值
        if (j + 1 < data.size() &&
                data.get(j).compareTo(data.get(j + 1)) < 0)
            j = rightChild(k);
        //data[j]是leftChild和rightChild中最大的

        if (data.get(k).compareTo(data.get(j)) >= 0)
            break;

        swap(k, j);
        k = j;
    }

}

Replace操作

Replace是指将堆中的最大元素取出,替换另一个进去。

自然地我们会想到使用之前的extractMax()和add()来实现,但是这样的时间复杂度将会是两次的O(log n),因此我们可以直接将堆顶元素替换以后执行sift down操作,这样时间复杂度就只有O(log n)。

Replace代码实现
//取出堆中最大的元素,替换为元素e
public E replace(E e){
    E ret = findMax();

    data.set(0, e);
    siftDown(0);

    return ret;
}

Heapify操作

Heapify是指将数组转化为堆

这里我们先将数组直接看成是一个完全二叉树,然后找到这棵二叉树的最后一个非叶子节点的节点,也就是该树的最后一个节点的父节点。然后从这个节点开始到根节点结束,执行sift down操作。

这样的时间复杂度为O(n)

Heapify代码实现
//heapify操作:将数组转化为堆
public MaxHeap(E[] arrs) {
    data = new ArrayList<>(Arrays.asList(arrs));
    for (int i = parent(data.size() - 1); i >= 0; i--) {
        siftDown(i);
    }
}