BinaryHeap
Какво представлява Heap-a ?
Heap-a представлява дървовидна структура от данни, в която елементите се подреждат по зададен ключ ( т.е има наредба в дървото ). Изпълнено е, че ако A e баща на B, то key(A) >= key(B). ( неравенството може да е обратно в зависимост от това дали е MinHeap или MaxHeap ).
Коренът на дървото, винаги представлява минималния( или максималния ) елемент с цел бърз достъп до него. При взимане на този елемент, той се изтрива и Хийп-а се преподрежда, така че винаги за корен да бъде съответният екстремен елемент ( минимален или максимален ).
Другото важно свойство на Heap-a е, че е почти пълно дърво ( балансирано ) и това ни позволява да го държим в масив, без да губим излишна памет.
Картинка, представляваща Binary MaxHeap.
Пояснение към картинката : 100 е най-голямото число и стои за корен на дървото. Всички елементи от лявото и дясното поддърво са по-малки от него.
Ляво поддърво : 19 е най-голямото число от лявото поддърво и всички елементи от неговото ляво и дясно поддърво са по-малки от него.
Дясно поддърво : Същото.
Този инвариант важи с рекурсвина сила за всяко поддърво в съответния минимален или максимален хийп.
Видове Хийп
Тук ще разгледаме Binary Heap-a, но не се завлуждавайте, че всичко в програмирането е двоично ;)
Може да разгледате в wikipedia различните видове.
// да се сложи таблицата със сравненията на различни хийпове и съответните сложности на операциите
Основни операции в Двоичен Хийп
- Добавяне на елемент (percolate up)
Алгоритъмът е следния :
- Слагаме новият елемент като листо в дървото, на първото свободно място
- Сравняват се новият елемент и баща му и ако не са в правилна наредба, се разменят
- Ако са в правилна наредба, елементът е добавен на правилното място.
Картинките показват добавянето на 15 в максимален хийп.
- Взимане на екстремния елемент ( минимален / максимален ) (percolate down)
Това е еквивалентно на триене на корена от дървото.
Алгоритъмът е следния :
- Слагаме последният елемент от дървото на мястото на корена
- Сравняваме с по-голямото ( по-малкото ) от двете му деца и ако не е изпълнена наредбата - разменяме ги
- В момента в който наредбата е изпълнена - спираме
Изтриване на корена от горния хийп :
Приложения
Най-честата употреба на Хийп-а е за реализация на приоритетна опашка , която от своя страна се използва в доста алгоритми, свързани с графи ( Дийкстра , Намиране на МПД с Прим ).
Друга честа употреба е сортиране, известно като heapsort
Реализация на Java
За реализацията се използва масив
Като съответно е пропуснат 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); // [ ] } }