Heapsort 实现做了太多的比较

Question

我刚刚实现了堆排序算法。我的目标是尽可能少地进行比较。我的实现有效，但比较次数是我在网上找到的这个示例的两倍多：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);
    }

我的问题是：我在哪个部分未能实现堆排序算法？哪里有不必要的比较？

它们必须在 sortNode 函数中。我把所有的比较都标上了评论。

我看不出如何改进此功能，以减少比较。这就是我的问题。

Answer 1

你实现的看起来不像堆排序（更准确地说，你使用的数据结构不是正确的二叉堆）。

sortNode 函数总是对其两个子函数进行递归调用，这导致一直遍历整个堆。这绝对不是堆的工作方式。所以所有额外的比较都来自一个不正确的算法（你的实现做 O(n ^ 2) 比较，而正确的应该只做 O(n log n)）。

如何解决？正如我上面所说，你知道的数据结构看起来不像堆，所以我建议从头开始正确实现堆（你可以阅读维基百科 article 以确保你正确理解它).

Heapsort 实现做了太多的比较

Heapsort implementation does too many comparisons

javascript

algorithm

sorting

comparison

heapsort