Реализация Heapsort делает слишком много сравнений

Question

Я только что реализовал алгоритм heapsort. Я стремлюсь к как можно меньшему количеству сравнений. Моя реализация работает, но делает вдвое больше сравнений, чем этот пример, который я нашел в Интернете: http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Sort/Heap/

Тестовая матрица: 6 2 3 1 5 4 2 5 1 6 7 4 3 2 6 7 3 2 5 6 1 8 7 5 4 3 2 1 5

Образец, который я нашел в Интернете, сделал 194 сравнения, чтобы отсортировать этот массив, моя реализация сделала 570 сравнений.

Вот код:

$(document).ready(function(){

        init();

        });

    var comparisons = 0;

    var init = function()
    {    
        var dataSource = getTestData();

        var root = {value: dataSource[0]};

        //Building heap
        for(var i = 1; i < dataSource.length; i++)
            addChild(root, {value: dataSource[i]});

        console.log("--- Source: ---")
        console.log(JSON.stringify(dataSource));

        console.log("--- Input: ---")
        console.log(JSON.stringify(dataSource));

        console.log("--- Tree: ---")
        console.log(JSON.stringify(root, null, 4));
        console.log("Nodes: " + countChildren(root));

        var sortedArray = new Array();
        comparisons = 0;

        //Do sorting here
        while(countChildren(root) != 0){
            sortNode(root); //Sorting heap
            sortedArray.unshift(root.value); //Adding the biggest entry from the top of the heap to the output
            deleteNode(root); //Removing the top of the heap
        }

        console.log("--- Sorted Tree: ---")
        console.log(JSON.stringify(root, null, 4));
        console.log("Nodes: " + countChildren(root));

        console.log("--- Sorted: ---")
        console.log(JSON.stringify(sortedArray));

        console.log("!!! Comparisons: " + comparisons + " !!!");
    }

    var deleteNode = function(item)
    {
        if (item.left == null && item.right == null)
            item.value = null;
        else if (item.left != null) {
            item.value = item.left.value;

            if (countChildren(item.left) == 1)
                item.left = null;
            else
                deleteNode(item.left)
        }
        else if (item.right != null) {
            item.value = item.right.value;

            if (countChildren(item.right) == 1)
                item.right = null;
            else
                deleteNode(item.right)
        }
    }

    var sortNode = function(item)
    {
        if (item.left != null && item.right == null){
            sortNode(item.left);

            comparisons++;
            if (item.value < item.left.value) //Comparison
            {
                var tmp = item.value;
                item.value = item.left.value;
                item.left.value = tmp;
            }
        }else if (item.right != null && item.left == null){
            sortNode(item.right);

            comparisons++;
            if (item.value < item.right.value) //Comparison
            {
                var tmp = item.value;
                item.value = item.right.value;
                item.right.value = tmp;
            }
        }
        else if (item.right != null && item.left != null) {
            sortNode(item.right);
            sortNode(item.left);

            //Some more comparisons
            var left_bigger_right = (item.right.value <= item.left.value);        comparisons++;
            var left_bigger_this = (item.value < item.left.value);                comparisons++;
            var right_bigger_this = (item.value < item.right.value);              comparisons++;

            if ((left_bigger_this && left_bigger_right) || (right_bigger_this && left_bigger_right)) {
                var tmp = item.value;
                item.value = item.left.value;
                item.left.value = tmp;
            }
            else if (right_bigger_this && left_bigger_right == false){
                var tmp = item.value;
                item.value = item.right.value;
                item.right.value = tmp;
            }
        }
        else{ //No children
            //Nothing to do :)
        }
    }

    var addChild = function(item, toAdd)
    {
        if(item.left == null)
            item.left = toAdd;
        else if (item.right == null)
            item.right = toAdd;
        else{ //if(item.left != null && item.right != null)
            childrenCountLeft = countChildren(item.left);
            childrenCountRight = countChildren(item.right);

            if (childrenCountRight < childrenCountLeft)
                addChild(item.right, toAdd);
            else if (childrenCountLeft < childrenCountRight)
                addChild(item.left, toAdd);
            else //if (childrenCountLeft == childrenCountRight)
                addChild(item.left, toAdd);
        }
    }

    var countChildren = function(item){
        var children = 0;

        if (item.value != null)
            children += 1;

        if (item.left != null)
            children += countChildren(item.left);
        if (item.right != null)
            children += countChildren(item.right);

        return children;
    }

    var getTestData = function(){
        return new Array(6 ,2 ,3 ,1 ,5 ,4 ,2 ,5 ,1 ,6 ,7 ,4 ,3 ,2 ,6 ,7 ,3 ,2 ,5 ,6 ,1 ,8 ,7 ,5 ,4 ,3 ,2 ,1 ,5);
    }

Мой вопрос: в какой части мне не удалось реализовать алгоритм heapsort? Где ненужные сравнения?

Они должны быть в функции sortNode. Я отметил все сравнения с комментариями.

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

Answer 1

То, что вы реализовали, не похоже на сортировку кучи (точнее говоря, используемая вами структура данных не является правильной двоичной кучей).

sortNode functions всегда делает рекурсивный вызов для обоих своих потомков, что приводит к обходу всей кучи все время. Это определенно не тот способ, которым должна работать куча. Таким образом, все дополнительные сравнения происходят от неправильного алгоритма (ваша реализация делает O(n ^ 2) сравнений, хотя правильный должен делать только O(n log n)).

Как исправить? Как я уже говорил выше, структура данных, которую вы знаете, не похожа на кучу, поэтому я рекомендую правильно реализовать кучу с нуля (вы можете прочитать статью в Википедии, чтобы убедиться, что вы правильно ее понимаете).