[数据结构与算法]DS-最大堆和优先队列

最大堆

堆概念

• 是一棵完全二叉树
• 父亲节点的优先级高于或低于左右孩子的优先级

完全二叉树

按照树的结构，从左到右依次排列

满二叉树

• 除叶子结点外所有的节点都有左右子树
• 叶子结点都在最后一层
• 第N层节点的个数：2^(N-1)
• 叶子结点个数：2^(h-1) h为高度
• 非叶子结点个数：2^(h-1) -1
• 总节点个数：2^h -1

最大堆概念

• 根节点索引为0，没有父亲节点
• 一个索引为 i 的节点的父亲节点的索引为：parent=i/(2-1) (根节点除外)
• 任意节点的左孩子索引为 left=2*(i-1)
• 任意节点的右孩子索引为 left=2*(i-1)+1

时间复杂度分析

• 上浮和下沉操作，最大交换次数为树的高度 h，时间复杂度为O(logn)
• 将一个元素插入到堆中，复杂度为O(logn)，所以，将n个元素逐个插入到一个空堆中，算法复杂堆为O(nlogn)
• heapify（整理）的过程时间复杂度为O(n)

最大堆实现

/**
 * 构建最大堆
 *
 * @author Deevan
 */
public class MaxHeap<T extends Comparable<T>> {

    private T[] data;   //存储堆中的数据
    private int size;   //堆中元素个数

    public MaxHeap() {
        this.data = (T[]) new Comparable[100];
        this.size = 0;
    }

    public MaxHeap(T[] arr) {
        this.data = Arrays.copyOf(arr, arr.length);
        this.size = arr.length;
    }

    /**
     * 判空
     */
    public boolean isEmpty() {
        return this.size == 0;
    }

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

    /**
     * 获取父节点索引
     */
    public int getParentIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index is error!");
        } else if (index == 0) {
            return -1;
        } else {
            return (index - 1) / 2;
        }
    }

    /**
     * 获取左孩子节点的索引
     *
     * @param index 索引
     */
    private int getLeftChildIndex(int index) {
        if (index < 0) {
            throw new IllegalArgumentException("index is invalid!");
        }
        return 2 * index + 1;
    }

    /**
     * 添加操作：先添加到数组最后，和其父元素比较交换，直至根节点或父亲结点的优先级高于当前结点
     */
    public void add(T ele) {
        //保存数据
        data[size] = ele;
        this.size++;
        //浮动到正确位置
        floatUp(size - 1);
    }

    /**
     * 上浮操作
     *
     * @param i 需要上浮元素的索引
     */
    private void floatUp(int i) {
        //找到父节点索引
        int parentIndex = getParentIndex(i);
        //与其父比较优先级
        while (i > 0 && data[i].compareTo(data[parentIndex]) > 0) {
            swap(this.data, i, parentIndex);
        }
    }

    /**
     * 交换
     *
     * @param arr         数组
     * @param curIndex    当前节点
     * @param changeIndex 交换的节点
     */
    private void swap(T[] arr, int curIndex, int changeIndex) {
        T temp = arr[curIndex];
        arr[curIndex] = arr[changeIndex];
        arr[changeIndex] = temp;
    }

    /**
     * swim（下沉）操作
     * 1、找到当前节点的左右孩子中较大的 与 当前节点进行比较
     * 2、如果孩子的优先级大，就交换
     * 3、直至叶子结点或左右孩子结点中优先级较高结点小于当前结点的优先级
     */
    private void swim() {
        if (isEmpty()) {
            return;
        }
        int curIndex = 0;
        int leftIndex = getLeftChildIndex(curIndex);
        int changeIndex = leftIndex;// 保存左右孩子优先级高的索引
        // 有左孩子的条件： leftIndex < this.size
        while (leftIndex < this.size) {
            //右孩子大，把右孩子赋给 交换索引
            if (leftIndex + 1 < this.size && data[leftIndex].compareTo(data[leftIndex + 1]) < 0) {
                changeIndex = leftIndex + 1;
            }
            //比较当前值与孩子交换值的大小
            if (data[curIndex].compareTo(data[changeIndex]) > 0) {
                break;
            }
            swap(this.data, curIndex, changeIndex);
            curIndex = changeIndex;
            leftIndex = getLeftChildIndex(curIndex);
            changeIndex = leftIndex;
        }
    }

    private void swim2() {
        if (isEmpty()) {
            return;
        }
        T rootEle = this.data[0];
        int curIndex = 0;
        int leftIndex = getLeftChildIndex(curIndex);
        int changeIndex = leftIndex;// 保存左右孩子优先级高的索引
        // 有左孩子的条件： leftIndex < this.size
        while (leftIndex < this.size) {
            if (leftIndex + 1 < this.size && data[leftIndex].compareTo(data[leftIndex + 1]) < 0) {
                changeIndex = leftIndex + 1;
            }
            if (rootEle.compareTo(data[changeIndex]) > 0) {
                break;
            }
            data[curIndex] = data[changeIndex];
            curIndex = changeIndex;
            leftIndex = getLeftChildIndex(curIndex);
            changeIndex = leftIndex;
        }
        data[curIndex] = rootEle;
    }
    
    /**
     * 获取优先级最高的元素
     */
    public T getPriorityFirst() {
        return data[0];
    }

    /**
     * 取出堆中最大的元素
     * 让最后一个元素替换第一个元素，然后进行下沉操作
     */
    public T removeMax() {
        if (isEmpty()) {
            throw new IllegalArgumentException("heap is null!");
        }
        T result = this.data[0];
        this.data[0] = this.data[size - 1];
        this.size--;
        swim2();
        return result;
    }

    /**
     * replace操作:取出优先级最高的元素，放入一个新元素---（让新元素替换索引为0的元素）
     */
    public void replace(T newEle) {
        this.data[0] = newEle;
        swim2();
    }

    /**
     * 将任意数组整理成最大堆
     * 方式一:  依次添加
     * 方式二:  从最后元素的父亲结点开始依次进行swim操作，直到root
     */
    public void heapify() {
        if (this.data == null || this.data.length == 0) {
            return;
        }
        for (int lastEleParentIndex = (this.data.length - 1 - 1) / 2; lastEleParentIndex >= 0; lastEleParentIndex--) {
            heapifySwim(this.data, lastEleParentIndex, this.data.length);
        }
    }

    /*
        1>先将第一个元素与最后一个元素交换，保证优先级最大的元素放到最后。然后对除最后一个结点之外的这棵树进行下沉操作
        2>在将第一个元素与倒数第二个元素交换，然后对除最后2个结点之外的这棵树进行下沉操作
        3>以此类推，直到根节点
     */
    private void heapifySwim(T[] arr, int lastEleParentIndex, int length) {
        int curIndex = lastEleParentIndex;
        int leftIndex = getLeftChildIndex(curIndex);
        int changeIndex = leftIndex;
        while (leftIndex < length) {
            if (leftIndex + 1 < length && arr[leftIndex].compareTo(arr[leftIndex + 1]) < 0) {
                changeIndex = leftIndex + 1;
            }
            if (arr[curIndex].compareTo(arr[changeIndex]) > 0) {
                break;
            }
            swap(arr, curIndex, changeIndex);
            curIndex = changeIndex;
            leftIndex = getLeftChildIndex(curIndex);
            changeIndex = leftIndex;
        }
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        int i = 0;
        while (i < size) {
            sb.append(this.data[i]);
            if (i != size - 1) {
                sb.append(",");
            }
            i++;
        }
        sb.append("]");
        return sb.toString();
    }
}

优先队列

普通队列： 先进先出

优先队列：出队顺序和入队顺序无关，和优先级有关。当访问元素时，优先级最高的会被删除。可以使用堆这种数据结构作为优先队列的底层结构

队列接口：

/**
 * 优先队列
 *
 * @author Deevan
 */
public class MySelfPriorityQueue<T extends Comparable<T>> implements Queue<T> {

    private MaxHeap<T> heap;

    public MySelfPriorityQueue() {
        heap = new MaxHeap<>();
    }

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

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

    @Override
    public void enqueue(T ele) {
        heap.add(ele);
    }

    @Override
    public T dequeue() {
        return heap.removePriorityFirst();
    }

    @Override
    public T getFront() {
        return heap.getPriorityFirst();
    }
}

pty() {
return heap.isEmpty();
}

@Override
public void enqueue(T ele) {
    heap.add(ele);
}

@Override
public T dequeue() {
    return heap.removePriorityFirst();
}

@Override
public T getFront() {
    return heap.getPriorityFirst();
}

}