Сложность пространства сортировки кучи

Я просто читал книгу Skiena Algorithm Design Manual, в частности раздел о сортировке кучей. Он заявляет, что

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

алгоритм в книге выглядит так:

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) и требует примерно вдвое больше памяти, а не «без дополнительной памяти»?


sorting algorithm space-complexity heapsort
person jcm    schedule 22.11.2014    source источник
comment
Надеюсь (и традиционно), куча устанавливается в массиве для сортировки.   -  person greybeard    schedule 22.11.2014
comment
@greybeard Я не уверен, что понимаю, что ты говоришь. Если вам дан несортированный массив, как вы можете преобразовать его (на месте) в кучу?   -  person jcm    schedule 22.11.2014
comment
(Вы заставляете меня задуматься о представлении в книге Скиены.) Преобразование массива на месте в произвольном порядке в неявную кучу (отношение предок ‹-› потомок определяется индексом массива) просто перестановка на месте, соответствующие имена операций — heapify и sift. Помимо основ, есть Wegener, чтобы спросить, какие ключи сравнивать, и < href="http://www.keithschwarz.com/smoothsort/" rel="nofollow noreferrer">гладкая сортировка для вариации, досадно недопредставленной, учитывая ее способность полностью использовать ранее существовавший порядок.   -  person greybeard    schedule 22.11.2014
comment
См. blog.mischel.com/2013/09/ 30/a-simple-heap-of-integers для описания и примера кода для упорядочения массива в куче.   -  person Jim Mischel    schedule 22.11.2014

Ответы (1)


arrow_upward
1
arrow_downward

Реализация пирамидальной сортировки, которую вы описали выше, не выглядит так, как будто она работает в постоянном пространстве именно по той причине, о которой вы беспокоитесь.

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

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

person templatetypedef    schedule 25.08.2015