將項目插入Max Heap

我不確定如何將項目插入到我的最大堆中，然後慢慢向上以使max heap屬性保持不變。如果heapArray已滿，我已經引發異常，因此無法插入項目。將項目插入Max Heap

我沒有使用JCF類或該程序的優先級隊列。我也引發了我的deleteMax方法，該方法刪除堆的最大值並恢復堆，使max heap屬性保持不變。

public class MaxIntHeap { 
//my global var's 
private int[] heapArray; // default size of 20 in constructor 
private int lastOne; //equal to size of the array(heap) 
private int size; 
private int k; 

public void heapInsert(int v) throws HeapException { 
    if(lastOne == heapArray.length - 1){ 
    throw new HeapException("The value " + v + " cannot be inserted because the heap is FULL!"); 
    } 
    else{ //This is where i am lost as to how i should insert 
    lastOne++; //size of lastOne is increased. 
}

這是我的removeMax方法。

public int removeMax()throws HeapException { 
    if(size == 0){ 
    throw new HeapException("The Heap is empty, therefore the Max value of the heap cannot be  
    removed."); 
    } 
    else{ 
    int max = heapArray[0]; 
    heapArray[0] = heapArray[lastOne]; 
    lastOne--; 
    k = 0; 
    while(k > 0){ 
     int j = k/2; 
     if(heapArray[k] < heapArray[j]){ 
      swap(heapArray[k], heapArray[j]); //swap method... 
      k = j; 

     } 
     else 
      break; 
    } 
    return max; 
    } 

    }

任何幫助將不勝感激。謝謝！

來源

2014-09-29 evilA

你的課堂設計看起來不錯。在堆：

leftChild = 2*parent +1 
rightChild = 2*parent + 2 
parent = (childindex-1)/2

對於maxheap，

在最後插入元件。然後將其與其父母進行比較。
如果父母大於這個最新的插入，你是好。
其他交換父母和這個孩子

重複，直到你到達根。

MaxHeapImpl：

public class MaxHeap { 

public int[] myHeap = new int[20]; 
public int begin = 0; 
public int current = 0; 

public int getParent(int index){ 
    return (index - 1)/2; 
} 

public int getLeftChild(int index){ 
    return 2*index+1; 
} 

public int getRighChild(int index){ 
    return 2*index+2; 
} 

public void insert(int data) { 

    myHeap[current] = data; 

    int i = current; 
    int tmp; 
    int parent; 
    while(i > 0){ 
     parent = getParent(i); 

     System.out.println(" I value"+i+" parent"+parent+" data"+data); 
     if(myHeap[parent] < myHeap[i]){ 
      tmp = myHeap[parent]; 
      myHeap[parent] = myHeap[i]; 
      myHeap[i] = tmp; 
     } else{ 
      break; 
     } 

     i = parent; 

    } 
    current++; 
}

}

識別TestClass：

public class MaxHeapTest { 

    @Test 
    public void test() { 
     MaxHeap myHeap = new MaxHeap(); 

     myHeap.insert(40); 
     myHeap.insert(20); 
     myHeap.insert(10); 
     myHeap.insert(25); 
     myHeap.insert(30); 
     myHeap.insert(100); 

     for(int i = 0; i < myHeap.current;i++){ 
      System.out.println(" "+myHeap.myHeap[i]); 
     } 
    } 

}

來源

2014-09-29 07:46:25 user892871

將項目插入Max Heap

回答

相關問題