数据结构--堆

2023-10-21

字数统计: 1k字 | 阅读时长≈ 4分

堆(一颗完全二叉树)：顺序存储结构，可用数组存储

大顶堆：每个父结点的值都大于其左右孩子的值
小顶堆：每个父结点的值都小于其左右孩子的值

数组中某个元素的父结点及其左右孩子索引:

父节点索引为i
- 左孩子索引：2*i+1
- 右孩子索引：2*i+2（左孩子索引+1）
孩子索引为j
- 父节点索引：(j-1)/2
最后一个非叶子结点索引：数组长度/2-1

/**
 * 大顶堆
 *
 * @author zzr
 * @create 2023-09-03-16:28
*/
public class MaxHeap implements Iterable{

    private int[] arr;//存储元素
    private int size;//堆元素个数
    private int cap;//堆容量

    /**
     * 默认容量11
    */
    public MaxHeap() {
        arr = new int[11];//优先队列初始容量
        size = 0;
        cap = 11;
    }

    /**
     * 根据给定数组调整成大顶堆
     *
     * @param arr
    */
    public MaxHeap(int[] arr) {
        this.arr = arr;
        this.size = arr.length;
        this.cap = arr.length;
        heapify();
    }

    /**
     * 根据给定容量创建
     *
     * @param n
    */
    public MaxHeap(int n) {
        arr = new int[n];
        size = 0;
        cap = n;
    }

    /**
     * 建堆（弗洛伊德建堆算法：时间复杂度O（n）先整体构建数组，在调整成堆）
     * （另一种威廉姆斯建堆算法：时间复杂度O（nlogn）边往数组添加元素，边调整成堆结构）
    */
    private void heapify() {
        //从最后一个非叶子结点开始，进行下潜操作
        for (int i = size / 2 - 1; i >= 0; i--) {
            down(i);
        }
    }

    /**
     * 下潜(递归)
     *
     * @param parent 父节点索引
    */
    private void down(int parent) {
        int left = parent * 2 + 1;//左孩子索引
        int right = left + 1;//右孩子索引
        int max = parent;
        //父节点、左孩子、右孩子三个中选择一个最大的
        if (left < size && arr[left] > arr[max]) {//左>父，则左大
            max = left;
        }
        if (right < size && arr[right] > arr[max]) {//右>左，则右更大
            max = right;
        }
        if (max != parent) {//左右孩子其中有一个比父节点大
            swap(max, parent);//进行交换
            down(max);//从max结点继续下潜
        }
    }

    /**
     * 交换
     *
     * @param i
     * @param j
    */
    private void swap(int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }


    /**
     * 扩容
    */
    private void grow() {
        if (size==cap) {
            int[] newArr = new int[cap += cap >> 1];//1.5倍
            System.arraycopy(arr, 0, newArr, 0, size);
            arr = newArr;
        }
    }

    /**
     * 上浮(非递归)
     *
     * @param x
    */
    private void up(int x) {
        int childVal = arr[x];
        int parent;
        while (x > 0) {
            parent = (x - 1) / 2;
            if (arr[parent] < childVal) {
                arr[x] = arr[parent];
            } else {
                break;
            }
            x = parent;
        }
        arr[x] = childVal;
    }

    /**
     * 添加元素
     *
     * @param v
     * @return
    */
    public boolean offer(int v) {
        grow();
        arr[size] = v;
        up(size);
        size++;
        return true;
    }

    /**
     * 查看堆顶元素
     * @return
    */
    public Integer peek(){
        if (size==0){
            return null;
        }
        return arr[0];
    }

    /**
     * 弹出堆顶元素
     * @return
    */
    public Integer poll(){
        if (size==0){
            return null;
        }
        int poll = arr[0];
        swap(0,size-1);
        size--;
        down(0);
        return poll;
    }

    /**
     * 获取堆元素个数
     * @return
    */
    public int getSize(){
        return size;
    }

    /**
     * 遍历
     * @return
    */
    @Override
    public Iterator iterator() {
        return new Iterator() {
            int i=0;
            @Override
            public boolean hasNext() {
                return i<size;
            }

            @Override
            public Object next() {
                return arr[i++];
            }
        };
    }

}

java 优先队列：PriorityQueue

参数可指定比较规则，如：
PriorityQueue< Integer > queue = new PriorityQueue();//默认小顶堆
PriorityQueue< Integer > queue = new PriorityQueue((a,b)->b-a);//大顶堆

常用方法：

add(E e)：将指定的元素添加到此队列中。
remove()：从此队列中删除并返回队头元素。如果队列为空，则抛出NoSuchElementException异常。
element()：返回队头元素但不删除它。如果队列为空，则抛出NoSuchElementException异常。
peek()：返回队头元素但不删除它。如果队列为空，则返回null。
size()：返回队列中的元素个数。
isEmpty()：如果队列为空，则返回true；否则返回false。
clear()：移除队列中的所有元素。
toArray(T[] a)：将队列中的元素复制到指定数组中。
offer(E e)：将指定的元素添加到此队列中。与add方法相同，但不会抛出IllegalStateException异常。
poll()：从此队列中删除并返回队头元素。如果队列为空，则返回null。
remove(Object o)：从此队列中删除第一次出现的指定元素（如果存在）。如果队列为空，则抛出NoSuchElementException异常。

本文作者： zzr
本文链接： http://zzruei.github.io/2023/10fe6957ee.html
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！