Куча Сортовая пространственная сложность

Question

Я просто читал книгу руководства по алгоритму алгоритма Skiena, в частности раздел «Сортировка кучи». Он утверждает, что

Это вроде на месте, то есть он не использует дополнительную память над массив, содержащий элементы, которые будут сортироваться

алгоритм в книге выглядит следующим образом:

heapsort(item_type s[], int n) 
{ 
    int i; 
    priority_queue q; 

    make_heap(&q, s, n); 

    for (i=0; i<n; i++) 
    s[i] = extract_min(&q); 
} 

Для меня это похоже на входной массив s элементов, мы создаем структуру данных кучи в переменной priority_queue. Разве это не означает, что требуемая пространственная сложность O (n) и требует примерно удвоенной памяти, а не «лишней памяти»?

Answer 1

Внедрение heapsort, которое вы описали выше, не похоже, что оно работает в постоянном пространстве именно по той причине, о которой вы беспокоитесь.

Однако это не значит, что это не возможно для реализации heapsort в O (1) вспомогательном пространстве. Как правило, реализация heapsort будет изменять порядок элементов в массиве, чтобы неявно хранить двоичную максимальную кучу. Одна из замечательных подробностей о макс-кучах заключается в том, что способ удаления из макс-кучи заключается в том, чтобы поменять корень узла (первый элемент массива) на самый правый лист (последний элемент в массиве, который является частью кучи) и затем пузырьком этот элемент вниз. Это означает, что вы можете многократно удалять из макс-кучи, заменяя первый элемент массива самым правым слотом в массиве, который не был заполнен, затем пузырьки сменили элемент на место. Для этого требуется только O (1) вспомогательное пространство для хранения и является типичным способом реализации heapsort.

Если вам интересно, у меня есть my own implementation of heapsort на моем личном сайте, на котором показано, как это сделать.