ヒープを実装する

Question

ヒープデータ構造を実装しようとしていますが、最大ヒープを構築するmaxHeapifyメソッドを作成し、最後に挿入して最大ヒープを維持するためにヒープを再配置する挿入メソッドで使用しました。 しかし、それは動作するようには表示されません、どんな助けていただければ幸いです。

public class Heap { // a class to implement a heap 
     private int[] data; // the heap array 
     private static final int FRONT = 1; 
     private int maxSize = 0; 
     private int currentSize; // the current size of the data in the array 

    public Heap(int maxSize) { 
     this.currentSize = 1; 
     this.maxSize = maxSize; 
     data = new int[maxSize + 1]; 
    } 

    public int[] getData() { 
     return data; 
    } 

    public void setData(int[] data) { 
     this.data = data; 
    } 

    public int getMaxSize() { 
     return maxSize; 
    } 

    public void setMaxSize(int maxSize) { 
     this.maxSize = maxSize; 
    } 

    public int getCurrentSize() { 
     return currentSize; 
    } 

    public void setCurrentSize(int currentSize) { 
     this.currentSize = currentSize; 
    } 

    @SuppressWarnings("unused") 
    private int parent(int index) {// the index of the parent 
     return index/2; 
    } 

    private int left(int index) { // the index of the left child 
     return (2 * index); 
    } 

    private int right(int index) { // the index of the right child 
     return (2 * index) + 1; 
    } 

    private void swap(int i, int j) { // to swap two elements 
     int temp = data[i]; 
     data[i] = data[j]; 
     data[j] = temp; 
    } 

    private void maxHeapify(int i) { // to build a max heap 
     int left = left(i); // a method to return the index of the left child 
     int right = right(i);// a method to return the index of the right child 
     int largest = i; 
     int x = currentSize; 
     if (left <= currentSize && data[left] > data[i]) { 
      largest = left; 
     } 
     if (right <= currentSize && data[right] > data[largest]) { 
      largest = right; 
     } 
     if (largest != i) { 
      int temp = data[i]; 
      data[i] = data[largest]; 
      data[largest] = temp; 
      maxHeapify(largest); 
     } 
    } 

    public void maxHeap() { 
     for (int i = currentSize/2; i >= 1; i--) { 
      maxHeapify(i); 
     } 
    } 

    public void insert(int newData) { // insert to the heap 
     data[currentSize] = newData; 
     currentSize++; 
     maxHeapify(FRONT); 


    } 

    public int deleteMax() { // delete max from the heap 
     int maxValue = data[FRONT]; 
     data[FRONT] = data[data.length - 1]; 
     maxHeapify(FRONT); 
     currentSize--; 
     return maxValue; 

    } 

    public void sort() {// heap sort 
     maxHeap(); 
     for (int i = maxSize; i > 1; i--) { 
      swap(FRONT, maxSize); 
      maxSize--; 
      maxHeapify(FRONT); 
     } 
    } 

    public void clear() { 
     maxSize = 0; 
    } 

    public boolean isEmpty() { 

     return maxSize == 0; 
    } 

    public boolean isFull() { 
     return currentSize == data.length; 
    } 

    public void printHeap() {// prints the heap 
     for (int i = 1; i <= maxSize/2; i++) { 
      System.out.print(
        " PARENT : " + data[i] + " LEFT CHILD : " + data[2 * i] + " RIGHT CHILD :" + data[2 * i + 1]); 
      System.out.println(); 
     } 
    } 
} 

Answer 1

あなたのヒープのルートに新しい番号を追加したときに動作しますmaxHeapifyあなたの機能。私はmaxHeapifyであなたがルートから子供に移動していると言っています。しかし、挿入中に最後に要素を挿入しています。あなたは下から上に移動する必要があります。

maxHeapify：ルートからダウン。

要素をデータ配列に挿入した後は、maxHeapifyの正反対で、子から親に上向きにチェックする必要があります。

Answer 2

これは動作するはずです：あなたが最後の位置に新しい要素を追加した後にシフトアップするために必要な

/** 
    * Parent. 
    * 
    * @param pos the pos 
    * @return the int 
    */ 
    private int parent(int pos) 
    { 
     return pos/2; 
    } 

    /** 
    * Left. 
    * 
    * @param pos the pos 
    * @return the int 
    */ 
    private int left(int pos) 
    { 
     return (2 * pos); 
    } 

    /** 
    * Right. 
    * 
    * @param pos the pos 
    * @return the int 
    */ 
    private int right(int pos) 
    { 
     return (2 * pos) + 1; 
    } 

    /** 
    * Checks if is leaf. 
    * 
    * @param pos the pos 
    * @return true, if is leaf 
    */ 
    private boolean isLeaf(int pos) 
    { 
     if (pos >= (size/2) && pos <= size) 
     { 
      return true; 
     } 
     return false; 
    } 

    /** 
    * Swap. 
    * 
    * @param fpos the fpos 
    * @param spos the spos 
    */ 
    private void swap(int fpos,int spos) 
    { 
     int tmp; 
     tmp = data[fpos]; 
     data[fpos] = data[spos]; 
     data[spos] = tmp; 
    } 

    /** 
    * Max heapify. 
    * 
    * @param pos the pos 
    */ 
    private void maxHeapify(int pos) 
    { 
     if (!isLeaf(pos)) 
     { 
      if (data[pos] < data[left(pos)] || data[pos] < data[right(pos)]) 
      { 
       if (data[left(pos)] > data[right(pos)]) 
       { 
        swap(pos, left(pos)); 
        maxHeapify(left(pos)); 
       }else 
       { 
        swap(pos, right(pos)); 
        maxHeapify(right(pos)); 
       } 
      } 
     } 
    } 

    /** 
    * Insert. 
    * 
    * @param newElement the element 
    */ 
    public void insert(int newElement) 
    { 
     data[++size] = newElement; 
     int current = size; 

     while(data[current] > data[parent(current)]) 
     { 
      swap(current,parent(current)); 
      current = parent(current); 
     } 
    } 

Answer 3

。 例を示します。

public void insert(int value) { 
      if (heapSize == data.length) 
        throw new HeapException(storage is overflow"); 
      else { 
        heapSize++; 
        data[heapSize - 1] = value; 
        siftUp(heapSize - 1); 
      } 
     } 
private void siftUp(int nodeIndex) { 
//code to hepify. 
}