Heap

Двоична пирамида. Брой на листата и брой на вътрешните върхове на пирамидата. Формули за индексите на родителя и на децата на даден връх, ако пирамидата е масив. Построяване на пирамида - анализ на сложността по време. Процедура Build Heap - наивна и бърза имплементация. Анализ на сложностите по време на двете имплементации. Пирамидална сортировка (Heapsort). Приоритетна опашка.

Що е то двоична пирамида (Binary Heap)

Формули за индексите на родителя и на децата на даден връх, ако пирамидата е масив

Реализацията на двоична пирамида с масив представлява следното нещо:
370px-Binary_tree_in_array.svg.png

Ако имаме възел i, може да вземем

  • индекс на левият син : 2*i + 1
  • индекс на десният син : 2*i
  • индекс на бащата : i/2

Heapsort

Нестабилен сортиращ алгоритъм, който използва (или имитира) структурата от данни "двоична пирамида", за да подреди дадените елементи.

Имплементации

Различни имплементации на различни езици :)

Имплементация на C с inplace сортиране

Имплементацията е взета от http://en.wikibooks.org/wiki/Algorithm_implementation/Sorting/Heapsort

#include <stdio.h>
void heapSort(int arr[], unsigned int N)
{
    int t; /* the temporary value */
    unsigned int n = N, parent = N/2, index, child; /* heap indexes */
    /* loop until array is sorted */
    for (;;) {
        if (parent > 0) {
            /* first stage - Sorting the heap */
            t = arr[--parent];  /* save old value to t */
        } else {
            /* second stage - Extracting elements in-place */
            n--;                /* make the heap smaller */
            if (n == 0) return; /* When the heap is empty, we are done */
            t = arr[n];         /* save lost heap entry to temporary */
            arr[n] = arr[0];    /* save root entry beyond heap */
        }
        /* insert operation - pushing t down the heap to replace the parent */
        index = parent; /* start at the parent index */
        child = index * 2 + 1; /* get its left child index */
        while (child < n) {
            /* choose the largest child */
            if (child + 1 < n  &&  arr[child + 1] > arr[child]) {
                child++; /* right child exists and is bigger */
            }
            /* is the largest child larger than the entry? */
            if (arr[child] > t) {
                arr[index] = arr[child]; /* overwrite entry with child */
                index = child; /* move index to the child */
                child = index * 2 + 1; /* get the left child and go around again */
            } else {
                break; /* t's place is found */
            }
        }
        /* store the temporary value at its new location */
        arr[index] = t;
    }
}
 
int main() {
 
    int N;
    scanf("%d", &N);
 
    int arr[N];
 
    for(int i = 0; i < N; ++i) {
        scanf("%d", &arr[i]);
    }
 
    heapSort(arr, N);
    for(int i = 0; i < N; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Имплементация на C++ със STL

#include <stdio.h>
#include <algorithm>
 
template <typename Iterator>
 
void heapSort(Iterator begin, Iterator end) {
    std::make_heap(begin,end);
    std::sort_heap(begin,end);
}
 
int main() {
 
    int N;
    scanf("%d", &N);
 
    int arr[N];
 
    for(int i = 0; i < N; ++i) {
        scanf("%d", &arr[i]);
    }
 
    heapSort(arr, arr + N);
    for(int i = 0; i < N; ++i) {
        printf("%d ", arr[i]);
    }
    return 0;
}

Имплементация на Приоритетна Опашка на Java

Намира се тук - http://fmi.wikidot.com/sdp-heap-java

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