Просеивание вверх в куче

В этом разделе рассказывается, как добавить элемент в максимальную кучу, что называетсясдвигом вверх。

Предположим, мы добавляем новый элемент 52 в максимальную кучу ниже, помещая его в последнюю позицию массива. Поскольку 52 больше своего родительского узла 16, свойство кучи не выполняется, и требуется корректировка.

Сначала поменяем местами значения по индексам 5 и 11 в массиве, то есть поменяем местами 52 и 16.

На данном этапе 52 всё ещё больше значения 41 по родительскому индексу 2, поэтому нужно переместить его ещё выше.

Теперь сравним 52 с 62. Поскольку 52 уже меньше своего родителя, его не нужно перемещать дальше вверх, и свойство максимальной кучи выполняется. Мы называем этот процесс сдвигом вверх для максимальной кучи.

Пример кода на Java

Загрузка пакета исходного кода:Скачать

Код файла src/example/heap/HeapShiftUp.java:

package example.heap;

/**
* Добавить элемент в кучу
 */
public class HeapShiftUp<T extends Comparable> {

    protected T[] data;
    protected int count;
    protected int capacity;

    // Конструктор, создаёт пустую кучу, которая может вместить capacity элементов
    public HeapShiftUp(int capacity){
        data = (T[])new Comparable[capacity+1];
        count = 0;
        this.capacity = capacity;
    }
    // Вернуть количество элементов в куче
    public int size(){
        return count;
    }

    // Вернуть boolean, указывающий, пуста ли куча
    public boolean isEmpty(){
        return count == 0;
    }
    // Вставить новый элемент item в максимальную кучу
    public void insert(T item){
        assert count + 1 <= capacity;
        data[count+1] = item;
        count ++;
        shiftUp(count);
    }
    // Поменять местами два элемента с индексами i и j в куче
    private void swap(int i, int j){
        T t = data[i];
        data[i] = data[j];
        data[j] = t;
    }

    //********************
    //* Основные вспомогательные функции max-кучи
    //********************
    private void shiftUp(int k){

        while( k > 1 && data[k/2].compareTo(data[k]) < 0 ){
            swap(k, k/2);
            k /= 2;
        }
    }

    // Тест HeapShiftUp
    public static void main(String[] args) {
        HeapShiftUp<Integer> heapShiftUp = new HeapShiftUp<Integer>(100);
        int N = 50; // Количество элементов в куче
        int M = 100; // Диапазон значений элементов кучи [0, M)
        for( int i = 0 ; i < N ; i ++ )
            heapShiftUp.insert( new Integer((int)(Math.random() * M)) );
        System.out.println(heapShiftUp.size());

    }
}
Другие расширения