Пирамидална структура от данни - Heap

BinaryHeap

Какво представлява Heap-a ?

Heap-a представлява дървовидна структура от данни, в която елементите се подреждат по зададен ключ ( т.е има наредба в дървото ). Изпълнено е, че ако A e баща на B, то key(A) >= key(B). ( неравенството може да е обратно в зависимост от това дали е MinHeap или MaxHeap ).
Коренът на дървото, винаги представлява минималния( или максималния ) елемент с цел бърз достъп до него. При взимане на този елемент, той се изтрива и Хийп-а се преподрежда, така че винаги за корен да бъде съответният екстремен елемент ( минимален или максимален ).
Другото важно свойство на Heap-a е, че е почти пълно дърво ( балансирано ) и това ни позволява да го държим в масив, без да губим излишна памет.
Max-heap.png
Картинка, представляваща Binary MaxHeap.
Пояснение към картинката : 100 е най-голямото число и стои за корен на дървото. Всички елементи от лявото и дясното поддърво са по-малки от него.
Ляво поддърво : 19 е най-голямото число от лявото поддърво и всички елементи от неговото ляво и дясно поддърво са по-малки от него.
Дясно поддърво : Същото.
Този инвариант важи с рекурсвина сила за всяко поддърво в съответния минимален или максимален хийп.

Видове Хийп

Тук ще разгледаме Binary Heap-a, но не се завлуждавайте, че всичко в програмирането е двоично ;)
Може да разгледате в wikipedia различните видове.
// да се сложи таблицата със сравненията на различни хийпове и съответните сложности на операциите

Основни операции в Двоичен Хийп

  • Добавяне на елемент (percolate up)

Алгоритъмът е следния :

  1. Слагаме новият елемент като листо в дървото, на първото свободно място
  2. Сравняват се новият елемент и баща му и ако не са в правилна наредба, се разменят
  3. Ако са в правилна наредба, елементът е добавен на правилното място.

Картинките показват добавянето на 15 в максимален хийп.
150px-Heap_add_step1.svg.png150px-Heap_add_step2.svg.png150px-Heap_add_step3.svg.png

  • Взимане на екстремния елемент ( минимален / максимален ) (percolate down)

Това е еквивалентно на триене на корена от дървото.
Алгоритъмът е следния :

  1. Слагаме последният елемент от дървото на мястото на корена
  2. Сравняваме с по-голямото ( по-малкото ) от двете му деца и ако не е изпълнена наредбата - разменяме ги
  3. В момента в който наредбата е изпълнена - спираме

Изтриване на корена от горния хийп :
150px-Heap_remove_step1.svg.png150px-Heap_remove_step2.svg.png

Приложения

Най-честата употреба на Хийп-а е за реализация на приоритетна опашка , която от своя страна се използва в доста алгоритми, свързани с графи ( Дийкстра , Намиране на МПД с Прим ).
Друга честа употреба е сортиране, известно като heapsort

Реализация на Java

За реализацията се използва масив
370px-Binary_tree_in_array.svg.png
Като съответно е пропуснат 0левият елемент, за по-лесно ( за мен ) смятане на индексите.
За връх с индекс i, левият син се намира на индекс 2 * i, а десният 2 * i + 1.

Първо ще започнем с interface-a за опашка ( защото Heap-a ще се ползва най-често като приоритетна опашка )

package heap;
/**
 * Основният интерфейс за Опашка
 * Операции : добавяне, махане, размер
 */
public interface Queue<E extends Comparable<E>> {
 
    /**
     * Добавя елемента отзад на опашката
     * @param element
     */
    public void add(E element);
 
    /**
     * @return Връща първият елемент от опашката
     */
    public E poll(); 
 
    /**
     * @return Броят елементи в опашката
     */
    public int size();
 
    /**
     * @return Дали опашката е празна
     */
    public boolean isEmpty();
}

И следният клас, който реализира интерфейс-а.
Представлява имплементация на минимален хийп.

package heap;
/**
 * Реализация на минимален хийп
 * Най-малкият елемент е винаги отгоре на дървото
 * и съответно първия елемент на опашката.
 */
public class MinHeap<E extends Comparable<E>> implements Queue<E> {
 
    private static final int DEFAULT_CAPACITY = 100;
 
    private int size;
 
    /**
     * Масивът, където ще държим дървото, което представлява хийп-а
     * 0-левата позиция няма да съдържа нищо и съответно релацията ще е :
     * data[i] - връх i
     * data[i/2] - бащата на връх i
     * data[i*2] - ляв син на връх i
     * data[i*2 + 1] - десен син на връх i
     */
    private E[] data;
 
    public MinHeap() {
        this(MinHeap.DEFAULT_CAPACITY);
    }
 
    @SuppressWarnings("unchecked")
    public MinHeap(int capacity) {
 
        data =(E[]) new Comparable[capacity + 1];
        size = 0;
    }
 
    /**
     * Конструктор, който строи Хйип-а по даден масив
     */
    @SuppressWarnings("unchecked")
    public MinHeap(E[] array) {
        data = (E[]) new Comparable[array.length + 1];
 
        for(int i = 0; i < array.length; i++)
            data[i+1] = array[i];
 
        size = array.length;
        buildHeap();
    }
 
    @Override
    public void add(E element) {
        if(size == data.length - 1)
            enlargeArray(data.length*2 + 1);
 
        int position = ++size; // взимаме следващата свободна позиция в масива и местим нагоре
 
        // percolate-up-ваме
        // position > 1 е проверка при добавяне на първият елемент
        while(position > 1 && data[position/2].compareTo(element) > 0) {
            data[position] = data[position/2];
            position /= 2;
        }
 
        // намерили сме позицията на елеманта и го поставяме
        data[position] = element;
    }
 
    @Override
    public E poll() {
        E min = data[1]; // понеже е MinHeap, най-малкият елемент стои отгоре
 
        // Като трием от Хийп, взимаме последният елемент
        // и го слагаме за корен, след което го "прецеждаме" надолу ( percolate down )
        E replace = data[size]; 
        data[1] = replace;
 
        data[size--] = null; // пазим чисто след нас
        if(size == 0)        
            data[1] = null;
 
        percolateDown(1); // пускаме помощната фукнция, за да прецеди елемента    
        return min;
    }
 
    /**
     * Взима елемента на позиция hole и го намества спярмо това, дали е Min/Max Heap
     * @param hole - позицията на елемента
     */
    private void percolateDown(int hole) {
        int child;
        E tmp = data[hole];
 
        // Докато не стигнем края на хйипа
        for(; hole * 2 <= size; hole = child) {
            child = hole * 2;
 
            // Взимаме по-малкият наследник ( ляв/десен )
            if(child != size && data[child+1].compareTo(data[child]) < 0)
                child++;
 
            // ако все още има елемент, който е по-малък от прецеждащия се - разменяме
            // иначе сме му намерили мястото и излизаме от цикъла
            if(data[child].compareTo(tmp) < 0)
                data[hole] = data[child];
            else
                break;
        }
        // слагаме елемента на мястото му
        data[hole] = tmp;
    }
 
    /**
     * Строим Хийп-а, когато ни е даден неподреден масив за параметър на конструктора
     */
    private void buildHeap() {
        for(int i = size / 2; i > 0 ; i--)
            percolateDown(i);
    }
 
    /**
     * Помощна функция, която създава нов масив с желания размер
     * и копира старите стойностти
     * @param capacity - размерът на новия масив
     */
    private void enlargeArray(int capacity) {
        E[] enlarged = (E[]) new Comparable[capacity];
        for(int i = 0; i < data.length; i++)
            enlarged[i] = data[i];
        data = enlarged;
    }
 
    @Override
    public int size() {
        return this.size;
    }
 
    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }
 
    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
 
        res.append("[ ");
        for(int i = 1; i <= size; i++) {
            res.append(data[i]);
            res.append(" ");
        }
        res.append("]");
        return res.toString();
    }
 
    public static void main(String[] args) {
 
        Integer[] a = {4,6,10,-1,3};
 
        MinHeap<Integer> pq = new MinHeap<Integer>(a);
 
        System.out.println(pq); // -1 3 10 6 4
 
        System.out.println("Polling min element : " + pq.poll()); // -1
 
        System.out.println(pq); // 3 4 10 6
 
        while(!pq.isEmpty())
            System.out.print(pq.poll() + " "); // 3 4 6 10
        System.out.println();
        System.out.println(pq); // [  ]
    }
}

Линкове по въпроса

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License