Алгоритм Heapsort с использованием min-heap

Question

Когда я реализую heapsort с помощью min-heap, он сортирует массив от наибольшего до наименьшего. Является ли это желаемым выходом для heapsort с использованием min-heap? Кажется излишним сортировать снова, чтобы вывести наименьшее значение в наибольшее после завершения сортировки, так как сам heap имеет самую маленькую и самую большую структуру.

КОД:

#include <iostream> 
#include <vector> 
#include "random.h" 
#include "print.h" 
int parent(int i) 
{ 
    return (i - 1)/2; 
} 
int left(int i) 
{ 
    if(i == 0) 
     return 1; 
    else 
     return 2*i; 
} 
int right(int i) 
{ if(i == 0) 
     return 2; 
    else 
     return 2*i + 1; 
} 
void min_heapify(std::vector<int> &A, int i, int heapsize) 
{ 
    int smallest; 
    int l = left(i); 
    //std::cout << "left = " << l << std::endl; 
    int r = right(i); 
    //std::cout << "right = " << r << std::endl; 
    if(l <= heapsize && A[l] < A[i]) 
     smallest = l; 
    else 
     smallest = i; 
    //std::cout << "smallest = " << smallest << std::endl; 
    if(r <= heapsize && A[r] < A[smallest]) 
     smallest = r; 
    if(smallest != i) { 
     print(A); 
     exchange(A, i, smallest); 
     min_heapify(A, smallest, heapsize); 
    } 
} 
void build_min_heap(std::vector<int> &A) 
{ 
    int heapsize = A.size() - 1; 
    for(int i = (A.size() - 1)/2; i >= 0; i--) 
     min_heapify(A, i, heapsize); 
} 
void heapsort(std::vector<int> &A) 
{ 
    int heapsize = A.size() - 1; 
    build_min_heap(A); 
    std::cout << "heapsort after buildmaxheap" << std::endl; 
    print(A); 
    for(int i = A.size() - 1; i > 0; i--) { 
     exchange(A, 0, i); 
     heapsize--; 
     std::cout << "heapsize = " << heapsize << std::endl; 
     min_heapify(A, 0, heapsize); 
    } 
} 
int main() 
{ 
    std::vector<int> B; 
    fill(B, 5); 
    print(B); 
    heapsort(B); 
    print(B); 
    return 0; 
} 

Выход из кода:

41 65 31 41 19 
41 65 31 41 19 
41 65 19 41 31 
41 19 65 41 31 
41 19 31 41 65 
19 41 31 41 65 
heapsort after buildmaxheap 
19 31 41 41 65 
heapsize = 3 
65 31 41 41 19 
31 65 41 41 19 
heapsize = 2 
heapsize = 1 
65 41 41 31 19 
heapsize = 0 
65 41 41 31 19 

Выход для 20 элементов:

41 65 31 41 19 15 72 11 78 69 37 23 29 63 75 4 5 49 75 99 
after buildmaxheap 
4 5 15 11 19 23 29 41 31 69 37 41 72 63 75 65 78 49 75 99 
after sort 
99 78 75 75 72 69 65 63 49 41 41 37 31 29 23 19 15 11 5 4 

Answer 1

Заказать: Используйте макс-heapify для сортировки в порядке asceding, мин-heapify отсортировать в порядке убывания.

Сортировка: Построение кучи с помощью min-heapify не сортирует ваш массив; она обеспечивает соблюдение только (слабее) мин-кучного свойство, то есть

A[parent(i)] <= A[i] 

для каждого узла i, отличного от корня. После того, как куча построена, корень (крайнее левое положение в массиве) имеет минимальный элемент. Сортировка затем неоднократно перемещает элементы из корня вправо и вызывает min-heapify в корне (приносит туда минимум того, что остается), следовательно, порядок убывания.

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

Answer 2

Обычно вы используете макс-кучи для сортировки в порядке возрастания, потому что это легче. Используя максимальную кучу, вы «плаваете» до максимума и стройте отсортированный список со спины.

Если вы хотите использовать мини-кучу для сортировки в порядке возрастания, вы должны построить ее обратно. (т.е. самый низкий является последний индекс). В противном случае вы будете размахивать своей кучей.

start 18 70 6 13 12 55 
min-heap(backwards) -> 18 70 55 13 12 6 
then 
swap 6 w 18 -> 6, 70 55 13 12 18 -> sink 18 -> 70 55 13 18 12 
swap 12 w 70 -> 6 12, 55 13 18 70 -> sink 70 -> 55 70 18 13 
swap 13 w 55 -> 6 12 13, 70 18 55 -> sink 55 -> 70 55 18 
swap 18 w 70 -> 6 12 13 18, 55 70 -> sink 70 -> 70 55 
swap 55 w 70 -> 6 12 13 18 55, 70 
done 

Answer 3

Я просто задавался вопросом об этой самой проблеме (это не сортировка кучи, имеющая дополнительный шаг в конце, ненужную замену элементов. Просто используйте мини-кучи и позвоните по телефону min-heapify и выполните свою работу).

Относительно этого способа мы могли бы достигнуть времени O (logn), которое несколько дисквалифицирует двоичную модель дерева решений, которая говорит, что O (nlogn) является приемлемой более строгой верхней границей алгоритмов сортировки сравнения.

Короткий ответ: Структура данных кучи не являются бинарными деревьями поиска. Куча может гарантировать упорядочение элементов в отсортированном виде сверху вниз, но двоичное дерево поиска гарантирует, что они будут упорядочены слева направо. Мы просто смешивали двоичные деревья и кучи.

мин кучного только гарантирует,

Amin[Parent]<=A[either_of_the_children] // says nothing about ordering of children 

Вот бинарное дерево (хотя несбалансированным и не отсортирован):

А вот Heap:

Надеюсь, вы поняли мою точку зрения. Если все еще нет, то подумайте об этом, поскольку мини-куча, представленная массивом, гарантирует, что родитель меньше своего ребенка, но ничего не говорит о том, все ли дети упорядочены в порядке слева направо? Мы по-прежнему будем выполнять min-heapify для каждого дочернего элемента текущего корня, который должен быть заменен.