разъяснения алгоритма гепсорта при фактической сортировке

Question

У меня есть вопрос о heapsort и о куче, участвующей в этом.

1. при построении meax-кучи из массива, на самом деле вы создаете что кучного автономный объект, или просто организовать массив, чтобы следующий алгоритм, чтобы построить кучу, чтобы построить из этого макс кучи ?

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

Алгоритм сделать это:

А - это пример массива: {5, 3, 17, 10, 19,84, 6, 22, 9}

пирамидальной сортировки (A)

1 BUILD-MAX-HEAP(A) 
// here you rearrange the array to represent a max heap or 
you actually construct a maxheap from that? 

//a max heap array representation will be: 
{84, 22, 17, 10, 19, 5, 6, 3, 9} 

2 for i = A.length downto 2{ 
3 exchange A[1] with A[i]; 
4 A.heap-size = A.heap-size - 1; -- what this do in fact? 
5 MAX-HEAPIFY(A, 1); 
} 

с моей точки зрения, кажется, на самом деле создать кучу массива размера (макс-кучу на самом деле). Затем на том, что делается на самом деле итерация, по-видимому, находится над массивом и MAX-HEAPIFY - теперь как-то на вскрикнувшей куче.

Можете ли вы разъяснить мне эти вещи шаг за шагом?

Answer 1

После некоторого времени, потраченного на поиск, я нашел, почему существует куча размера, а также массив.length (массив на самом деле является объектом, где представлена ​​куча). Если вы не хотите, чтобы на хвосте массива было больше свободных пятен, и когда вы добавляете элемент в кучу, вы увеличите размер массива только с одним пятном, тогда вам действительно не нужен размер кучи, потому что они будут всегда одинаковыми, и это array.length.

Однако, если вы это сделаете, это будет наивная реализация кучи над массивом, потому что каждый раз, когда вы добавляете или удаляете/извлекаете элемент в/из кучи/массива, стоимость этой операции будет O (n), потому что вам придется скопировать значения старого массива в новый массив.

Но когда мы удаляем/извлекаем узел, мы не сокращаем фактически массив, операция удаления будет стоить нам в макс/мин-куче O (log n), почему?

, когда мы убираем пункт/узел - на самом деле корень - из кучи мы просто сделать следующее: (упростить вещь, которую мы будем использовать Int)

1 store the root in auxiliary variable: int returnObj = array[0]; cost O(1) 
2 put the value from the last element of the heap(why not array because only the heap-size 
will decrease, the array length is the same) into the first 
heap/array element array[0]=array[heap-size-1]; heap-size at the beginning == array.length 
2.1 right now we have have last element ==first element, 
and we need to shrink the heap represented on the array somehow. 
Now comes the reason to have a heap-size variable independent of array.length if we don't 
want to actually shrink the array because that operation will cost us O(n-1) time 
- instead of doing that we will use an auxiliary variable heap-size, 
as i mentioned above-to mark the end of the heap, to be able to ignore tail elements of the 
array that actually are not part of the heap any-more. 
2.2 because right now the first element of the array and also is the first element of 
the heap is actually one of the smallest - i am saying is one of the smallest because 
it is not mandatory that the last element to be the smallest to satisfy the heap property, 
example {84, 22, 17, 10, 19, 5, 6, 3, 9} is a max-heap - 
we need to call max-hipify over array[0] ... to ... array[heap-size] to recreate the max-heap 
again. That will cost us O(log n) in the worst case, much less than O(n). 

3 return returnObj;