将项目插入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

回答

相关问题