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

Question

Я только что реализовал алгоритм heapsort. Im, стремясь как можно меньше сравнений. Моя реализация работает, но делает более чем в два раза больше сравнений, чем этот образец, который я нашел онлайн: 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)).

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