Heapsort

Я нашел код для пирамидальной сортировки по адресу: http://rosettacode.org/wiki/Sorting_algorithms/Heapsort#C

Насколько я понимаю (что где-то неправильно), так это то, что функция heapsort() имеет два цикла. Первый цикл предназначен для создания структуры кучи (минимальной или максимальной), а второй цикл — для фактической сортировки двойников. Но я думаю, что у меня первая петля неправильная.

Весь код выглядит так

#include <stdio.h>
#include <stdlib.h>

#define ValType double
#define IS_LESS(v1, v2)  (v1 < v2)

void siftDown( ValType *a, int start, int count);

#define SWAP(r,s)  do{ValType t=r; r=s; s=t; } while(0)

void heapsort( ValType *a, int count)
{
    int start, end;

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

    for (end=count-1; end > 0; end--) {
        SWAP(a[end],a[0]);
        siftDown(a, 0, end);
    }
}

void siftDown( ValType *a, int start, int end)
{
    int root = start;

    while ( root*2+1 < end ) {
        int child = 2*root + 1;
        if ((child + 1 < end) && IS_LESS(a[child],a[child+1])) {
            child += 1;
        }
        if (IS_LESS(a[root], a[child])) {
            SWAP( a[child], a[root] );
            root = child;
        }
        else
            return;
    }
}


int main()
{
    int ix;
    double valsToSort[] = {
        1.4, 50.2, 5.11, -1.55, 301.521, 0.3301, 40.17,
        -18.0, 88.1, 30.44, -37.2, 3012.0, 49.2};
#define VSIZE (sizeof(valsToSort)/sizeof(valsToSort[0]))

    heapsort(valsToSort, VSIZE);
    printf("{");
    for (ix=0; ix<VSIZE; ix++) printf(" %.3f ", valsToSort[ix]);
    printf("}\n");
    return 0;
}

Мой вопрос: почему цикл /heapify/ начинается с (count-2)/2?

фрагмент из heapsort() здесь:

    /* heapify */
    for (start = (count-2)/2; start >=0; start--) {
        siftDown( a, start, count);
    }

ОБНОВЛЕНИЕ

Я думаю, что, возможно, я только что ответил на свой вопрос, но это потому, что мы должны установить структуру кучи, где частичный фокус цикла направлен на создание сбалансированного дерева? То есть в кучах должны быть заполнены все уровни, кроме последнего. Это правильное мышление?


c sorting heap heapsort
person kendall    schedule 05.12.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Для нечетного счета первой дочерней парой для heapify является [((count-2)/2)*2 + 1] и a[((count-2)/2)*2 + 2], последние два элемента массив. Для четного счета дочерний элемент-соло находится в [((count-2)/2)*2 + 1], последнем элементе массива. Это отправная точка для наполнения всего массива. Во втором цикле нужно только повторно наполнить массив в основном кучей [от 0 до конца] по мере уменьшения конца.

Вики-статья:

http://en.wikipedia.org/wiki/Heapsort

person rcgldr    schedule 05.12.2015
comment
вы говорите, что это ((count-2)/2)*2, но это не то, что я вижу, нет *2. и кроме того, зачем было бы, если бы просто отменить с помощью /2 ? ржунимагу - person kendall; 06.12.2015
comment
@kendall в heapsort() start = (count-2)/2 (округлено вниз, целочисленное деление). В siftdown() дочерний элемент = root*2 + 1, второй дочерний элемент — это child + 1 = root*2 + 2. - person rcgldr; 06.12.2015