Сортировка массива при помощи бинарного дерева

Как можно отсортировать массив при помощи бинарного дерева?

ето касательно так называемого алгоритма сортировки при помощи кучи (heap sort). я в своё время о нём читал, не помню правда, понял или нет, но выяснил одно: по сложности он эквивалентен обычной быстрой сортировке, но работает как правило медленнее. тебе надо поискать heap sort в поисковике или на сайтах, упомянутых в топике "ссылки на алгоритмы и способы их реализации".

При чем тут heap sort? Heap sort это другое, там, конечно, что-то вроде дерева тоже имеется, но в каждый фиксированный момент времени там известен лишь только самый минимальный (или максимальный) элемент, а второй (или предпоследний) элемент не определен.

Сортировка с помощью бинарного дерева - это самая тривиальная сортировка, которая только приходит в голову: когда добавляешь новый элемент, то сравниваешь его с элементом вершины и в зависимости от результата сравнения отсылаешь его либо в левую либо в правую ветку (либо оставляешь вместо бывшего верхнего элемента, а его в свою очередь отправляешь либо в лево либо в право) и т. д. пока он не займет нужное место. В случае равномерно распределенных случайных чисел сложность составляет O(N*Log(N)), в худшем случае сложность O(N^2).

Пример

<br>            7<br>          /   \<br>        5      10<br>       / \     / \<br>      2   6   9  12<br>

<br>void HeapSort(int N) {<br> int x;<br> int l=(N/2)+1;<br> int r=N;<br> while (l>0) {l--; shift(l,r); }<br> while (r>0) {<br>   x=mas[0]; <br>   mas[0]=mas[r]; <br>   mas[r]=x;<br>   r--; shift(l,r);<br> }<br>}<br><br>void shift(int l,int r) {<br> int x=mas[l];<br> int i=l;<br> int j=2*l;<br> if ((j<r)&&(mas[j]<mas[j+1])) j++;<br> while ((j<=r)&&(x<mas[j])) {<br>   mas[i]=mas[j];<br>   i=j;   <br>   j=2*j;<br>   if ((j<r)&&(mas[j]<mas[j+1])) j++; <br> }<br> mas[i]=x;<br>}<br>

N - длина массива
так вроде

Цитата Serega_f1, 28.03.03, 12:34:59

<br>void HeapSort(int N) {...

...

Все равно, heap sort и сортировка бинарным деревом - это разные вещи.
Теоретически, heap sort должна работать быстрее дерева, поскольку в ней
содержится меньше информации.

Цитата

Сортировка с помощью бинарного дерева - это самая тривиальная сортировка, которая только приходит в голову: когда добавляешь новый элемент, то сравниваешь его с элементом вершины и в зависимости от результата сравнения отсылаешь его либо в левую либо в правую ветку (либо оставляешь вместо бывшего верхнего элемента, а его в свою очередь отправляешь либо в лево либо в право) и т. д. пока он не займет нужное место. В случае равномерно распределенных случайных чисел сложность составляет O(N*Log(N)), в худшем случае сложность O(N^2).

Каким же именно образом происходит сравнение элементов? Другими словами: отчего зависит попадание
потомка либо влево, либо вправо, либо на место предка.
Мне известно, что в бинарном дереве потомок слева должен быть меньше своего предка, а потомок справа - наоборот,
больше предка. Тут условия сравнения вполне понятны. Но при каком условии потомок встает на место предка - вот
вопрос?
Разъясните мне пожалуйста, прогу на неделе сдавать надо...

Наверное, имеется в виду то, что потомок справа меньше или равен своего предка, а потомок слева строго меньше. Соответственно при вставке совпадающего элемента он идет направо.

Добавлено 23.11.04, 19:15
wormball, heap sort всегда работает за O(n*log(n)) в отличие от быстрой сортировки. При этом по времени heap sort всегда быстрее quick sort'а. Особенно это сказывается на массивах следующего вида: очень много элементов, но диапазон их изменения очень мал. Вот здесь quick sort даже медленне, чем bubble sort. Причем, по памяти quick sort тоже более требователен чем heap sort (quick sort требует O(log(n)) в лучшем случае, O(n) в худшем, heap sort - O(1) памяти в худшем случае).

А может быть, имеется в виду то, что дерево должно быть сбалансированным. То есть, все веточки примерно одинаковой длины. Есть специальные алгоритмы балансировки при добавлении, при них корень действительно потомок иногда встает на место предка.

специально по этому случаю выботал heap sort. книжка называется "жемчужины программирования". нормального русскоязычного объяснения я в инете не нашёл, валяются одни реализации, поэтому попробую объяснить своими словами.

итак, кучей (heap) (не путать с динамической памятью и кучами дерьма) называется такое двоичное дерево, что:
1. значение предка не больше значений потомков.
2. "все веточки примерно одинаковой длины". то есть длины отличаются не более чем на 1.
3. все длинные веточки сгруппированы слева.

например

кучи
       21
     /    \
   23     48
  /  \   /  \
 37  29 85  48
 
        1
     /    \
    2     3
  /  \
 4   5  
 
не кучи
       15
     /    \
   23     65 <- 65 больше, чем 48 (нарушение п. 1)
  /  \   /  \
 37  29 85  48
 
         1
       /   \
      2     3
    /  \
   4   5  
 /  \
 6  7    <- ветви оканчиваются на трёх уровнях (нарушение п. 2)
 
       1
     /   \
    2     3
  /        \
 4          5  <- потомки не сгруппированы (нарушение п. 3)

прикол в том, что деревья подобного вида (удовлетворяющие пп. 2 и 3) можно организовать с помощью массива, не прибегая к указателям. например, вышеприведённые кучи будут выглядеть так:

21 23 48 37 29 85 48
1 2 3 4 5

, то есть все вершины записываются туда по порядку, начиная с первого уровня. при этом всегда можно восстановить вид дерева, пользуясь свойствами 2 и 3. адреса предков и потомков вершины с номером n будут выражаться так(массив нумеруется с единицы, а не с нуля):
предок(n) = n/2 (или n shr 1) (целочисленное деление на 2)
левый потомок(n) = n*2 (или n shl 1)
правый потомок(n) = n*2+1 (или n shl 1 + 1)

при этом наименьший элемент кучи всегда будет в её начале.

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

просеивание вверх
       21
     /    \
   23     48
  /  \   /  \
 37  29 85  17<новый елемент
 
       21
     /    \
   23     17<
  /  \   /  \
 37  29 85  48
 
       17<
     /    \
   23     21
  /  \   /  \
 37  29 85  48

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

просеивание вниз
       10<
     /    \
    2     3
  /  \
 4   5  
 
       2
     /  \
   10<   3
  /  \
 4   5  
 
       2
     /  \
    4    3
  /   \
 10<   5

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

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

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

Цитата mo3r, 23.11.04, 22:11, 521110

wormball, heap sort всегда работает за O(n*log(n)) в отличие от быстрой сортировки

правильно

Цитата mo3r, 23.11.04, 22:11, 521110

При этом по времени heap sort всегда быстрее quick sort'а

автор книжки мерял, у него получилось, что медленнее

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

мож у тебя quicksort был паршивый?

wormball, нет, я специально делал несколько вариантов и выбрал наилучший. Тот вариант, который в стандартной поставке BP7.0\Examples\DOS\QuickSort.pas даже не принимался в расчет. В принципе, можно повторить замеры производительности. Я постараюсь найти ту программу, которой я пользовался. Кстати, если ты предложишь вариант QuickSort, который будет работать быстрее HeapSort, то это будет очень интересно.

ну, то что это неплохая реализация это точно:

var
    a: array of longint;
    c, i: longint;
 
procedure qs( l, r: longint);
var
    i, j, m: longint;
begin
    i := l;
    j := r;
    m := a[l + random(r - l + 1)]; //тут избавляемся от возможной квадратичной скорости
    while i <= j do begin
        while a[i] < m do inc(i);
        while a[j] > m do dec(j);
        if i <= j then begin
            c := a[i];
            a[i] := a[j];
            a[j] := c;
            inc(i);
            dec(j);
        end;
    end;
    if l < j then qs(l, j);
    if i < r then qs(i, r);
end;

А, вообще, qsort в среднем работает ~ в 4 раза быстрее сортировки кучей. (это из олимпиадной практики)

Итак, результат. Я оказался неправ. Причина, скорее всего, в реализациях qsort, которые я проверял. Предложенный qsort работает в 2 раза медленнее, чем написанный мною heapsort. Причем в независимости от характера исходных данных. (Исключая вариант с очень небольшими границами изменениями элементов массива).

Цитата mo3r, 30.11.04, 15:42, 528287

Я оказался неправ.

Цитата mo3r, 30.11.04, 15:42, 528287

Предложенный qsort работает в 2 раза медленнее, чем написанный мною heapsort.

Так ты ведь и говорил, что qsort медленнее работает:

Цитата mo3r, 29.11.04, 19:38, 527232

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

Покажи свою реализацию heap-sort'а очень интересно посмотреть