heapSort issues java

Question

Ищете несколько простых советов по исправлению моей кучи. Надеюсь, это нечто простое, что я не понимаю.

У меня возникли проблемы с моими методами dumpHeap() и extractMax(). Кажется, что он помещает dumpheap в порядок, но добавляет 0 к моему массиву. Это по-прежнему технически куча, но беспокоит меня, почему появляется 0.

Другой вопрос: мой extractMax не будет извлекать максимальные числа в порядке убывания, которые перечисляют числа, которые были извлечены.

Мои выходы чтения, которые являются неправильными:

Исходный массив: 10 2 8 4 18 20 3 16 5

Макс-кучного: 20 18 16 10 8 4 2 3 0 5

Экстракт Максимальный: 20 5 0 3 2 4 8 10 16

Если бы я мог получить несколько советов, где искать/менять вещи, было бы весьма полезно.

Спасибо!

public class heap { 

    public int size; 
    public int [] H; 
    public int position; 

    public heap(int size) 
    { 
      this.size=size; 
      H = new int [10]; 
      position = 0; 
    } 

    public void createHeap(int [] arrA) 
    { 
      if(arrA.length>0) 
      { 
        for(int i=0;i<arrA.length;i++) 
        { 
          insert(arrA[i]); 

        } 
      }   
    } 

    public void dumpHeap() 
    { 
      for(int i=0;i<H.length;i++) 
      { 
        System.out.print(" " + H[i]);    
      } 
      System.out.println(""); 
    } 

    public void insert(int x) 
    { 
      if(position==0) 
      { 
         H[position]=x; 
         position = 2; 
      }else{ 
         H[position++]=x; 
         exchange(); 
       } 
    } 

    public void exchange() 
    { 
      int pos = position-1; 
      while(pos > 0 && H[pos] > H[pos/2]) 
      { 
        int y = H[pos]; 
        H[pos]=H[pos/2]; 
        H[pos/2] = y; 
        pos = pos/2; 
      } 
    } 

    public int extractMax() 
    { 
      int max = H[0]; 
      H[0]=H[position-1]; 
      H[position-1]= 0; 
      position--; 
      extractSort(0); 
      return max; 
    } 

    public void extractSort(int k) 
    { 
      int a = H[k]; 
      int maxNum =k; 
      if(2*k>position && H[maxNum]<H[2*k]) 
      { 
        maxNum = 2*k; 
      } 

      if(2*k+1>position && H[maxNum]<H[2*k+1]) 
      { 
        maxNum = 2*k+1; 
      } 

      if(maxNum!=k) 
      { 
         swap(maxNum,k); 
         extractSort(k); 
      } 

    } 

    public void swap(int a, int b) 
    { 

      int temp = H[a]; 
      H[a] = H[b]; 
      H[b] = temp; 
    } 
} 

public class heapMain { 


    public static void main(String args[]) 
    { 
      int arrA [] = {10,2,8,4,18,20,3,16,5}; 
      System.out.print("Original Array : "); 
      for(int i=0;i<arrA.length;i++) 
      { 
        System.out.print(" " + arrA[i]); 
      } 

      heap h = new heap(arrA.length); 
      System.out.print("\nMax-Heap : "); 
      h.createHeap(arrA);  
      h.dumpHeap(); 

      System.out.print("Extract Max :"); 
      for(int i=0;i<arrA.length;i++) 
      { 
        System.out.print(" " + h.extractMax()); 
      } 
    } 
} 

Answer 1

Я думаю, вы перепутались с индексом массива.

Согласно вам функция вставки, вы пропустили индекс 1 и установили позицию на 2, что оставит H[1] a 0, и именно поэтому вы видите 0 на dumpHeap().

Если вы пытаетесь реализовать кучу, как here, у вашего исходного алгоритма выбора индекса в exchange() есть некоторые проблемы. Родитель индекса 1 является индексом 0, а родительский индекс индекса 2 и 3 - индексом 1. Этот алгоритм может быть прекрасным, если вы пропустите индекс 0 во всех своих методах, но, похоже, вы смешиваетесь с ними.

первый, не пропустите индекс 1 в insert()

public void insert(int x) 
{ 
    H[position++] = x; 
    exchange(); 
} 

2, рассчитать родителя и индекс ребенка правильно.

public void exchange() 
{ 
    int pos = position-1; 
    int parentPos = (pos-1)/2; 
    while(pos > 0 && H[pos] > H[parentPos]) 
    { 
    int y = H[pos]; 
    H[pos]=H[parentPos]; 
    H[parentPos] = y; 
    pos = parentPos; 
    parentPos = (pos-1)/2; 
    } 
} 

третьего, используйте правильное состояние в extractSort()

public void extractSort(int k) 
    { 
     int baseValue = H[k]; 
     int maxNumPos =k; 
     int lhsPos = 2*k+1; 
     int rhsPos = 2*k+2; 
     if(lhsPos < position && H[maxNumPos] < H[lhsPos]) 
     { 
      maxNumPos = lhsPos; 
     } 
     if(rhsPos < position && H[maxNumPos] < H[rhsPos]) 
     { 
      maxNumPos = rhsPos; 
     } 

     if(maxNumPos!=k) 
     { 
        swap(maxNumPos,k); 
        extractSort(maxNumPos); 
     } 
    } 

Выход может быть то, что вы хотите.

Исходный массив: 10 2 8 4 18 20 3 16 5

Макс-кучного: 20 16 18 10 4 8 3 2 5

Экстракт Макс: 20 18 16 10 8 5 4 3 2