Сортировка кучей и приоритетная очередь

Java задняя часть Google

куча

Когда дело доходит до куч, мы должны говорить о двоичных деревьях.Двоичное дерево относится к дереву, в котором каждый узел может содержать не более двух дочерних узлов. Обычно используемые реализации двоичных деревьев — это двоичное дерево поиска (BinarySearchTree) и двоичная куча (BinaryHeap).

Понятие дерева здесь повторяться не буду, если вам нужно самому погуглить, то бинарная куча на самом деле соответствует полному бинарному дереву, за исключением последнего слоя. Следовательно, куча может храниться в массиве, а двоичная куча делится на большую корневую кучу и маленькую корневую кучу.На следующем рисунке показано соответствие между большой корневой кучей и массивом.

image

Следовательно, массив, соответствующий узлу кучи, может быть легко получен. :банан:

  • родительский узел parent = индекс / 2
  • Левый узел слева = индекс * 2
  • Правый узел справа = индекс * 2 + 1

сортировка кучей

Сортировка кучи состоит в том, чтобы вынуть максимальное число в верхней части максимальной кучи, продолжить корректировку оставшейся кучи до максимальной кучи и снова вынуть максимальное число в верхней части кучи.Этот процесс продолжается до тех пор, пока не останется только один оставшийся номер. В куче определены следующие операции:

  • Max-Heapify: Настройте дочерние узлы в конце кучи так, чтобы дочерние узлы всегда были меньше, чем родительские узлы.
  • Build-Max-Heap: переупорядочить все данные в куче, чтобы сделать ее максимальной кучей.
  • Сортировка кучей (Heap-Sort): удалите корневой узел, расположенный в первых данных, и выполните рекурсивную операцию максимальной настройки кучи.

Простое объяснение:Настройка максимальной кучи (Max-Heapify) на самом деле является одноразовой.Процесс создания максимальной кучи (Build-Max-Heap) таков:каждый узелмаксимальная настройка кучи, сортировка кучей (Heap-Sort) каждый размаксимальная куча созданаЗатем вам нужно преобразовать самый большой элемент.

Подводя итог в одном предложении: каждый узел дерева циклов тонет, затем отделяется и продолжает цикл. :tomato:

На следующем рисунке показан процесс погружения:

picture

приоритетная очередь

Обычные очереди удовлетворяют требованиям очередей «первым пришел», «первым обслужен» и «приоритет» удовлетворяют тому, что каждый раз, когда из очереди выходит элемент с наивысшим приоритетом. :strawberry:

Существует три общих реализации приоритетных очередей:

  • Отсортированный массив (добавлять в отсортированную позицию при добавлении, удалять хвостовой элемент при опросе)
  • Неупорядоченный массив (добавлять непосредственно в конец очереди при добавлении, находить приоритетный элемент при опросе)
  • Двоичная куча (плавает при добавлении, тонет при опросе)

image

Связь между приоритетной очередью и сортировкой в ​​куче

Поскольку очереди с приоритетом нужен только элемент с максимальным приоритетом для каждого опроса, нет необходимости поддерживать порядок всей двоичной кучи, только корневой узел должен соответствовать максимальному приоритету. Следовательно, на корневом узле необходимо выполнить только одну операцию Max-Heapify с сортировкой кучей.

Анализ исходного кода приоритетной очереди Java

    

    //add方法也就是直接调用offer方法
    public boolean offer(E e) {
        //不允许插入null
        if (e == null)
            throw new NullPointerException();
        modCount++;
        int i = size;
        //容量不够则进行扩容
        if (i >= queue.length)
            grow(i + 1);
        siftUp(i, e);//这里调用了上浮
        size = i + 1;
        return true;
    }
    
    //上浮分为两种情况，判断是否设置了comparator
    private void siftUp(int k, E x) {
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            siftUpComparable(k, x);
    }

    //我们只分析这种没有设置comparator的方法，另一种类比
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            //找到父节点
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            //如果当前节点大于父节点则上浮结束
            if (key.compareTo((E) e) >= 0)
                break;
            //否则，将父节点下沉
            queue[k] = e;
            k = parent;
        }
        //将节点赋值到正确的上浮位置
        queue[k] = key;
    }
    
    //poll方法
    public E poll() {
        //如果没有元素，则返回null
        if (size == 0)
            return null;
        int s = --size;
        modCount++;
        //返回根节点
        E result = (E) queue[0];
        E x = (E) queue[s];
        //将队尾元素移到根节点，并进行下沉
        queue[s] = null;
        //队列中不止一个元素，则进行下沉
        if (s != 0)
            siftDown(0, x);
        return result;
    }
    
    //下沉方法的实现与上浮类似，就不赘述了。
Категории