java - 将项目插入最大堆

Question

我不知道如何将一个项目插入我的最大堆然后涓涓细流以保持最大堆属性。如果 heapArray 已满因此无法插入项目，我会抛出异常。

我没有为此程序使用 JCF 类或优先级队列。我还抛出了我的 deleteMax 方法，该方法删除了堆的最大值并恢复了堆，因此最大堆属性保持不变。

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;
   }

  }

任何帮助将不胜感激。谢谢！

score 1 · Accepted Answer

你的班级设计看起来不错。在堆中：

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

对于一个最大堆，

最后插入元素。然后将其与其父级进行比较。
如果 parent 大于此最新插入，则很好。
其他交换父母和这个孩子

重复直到到达根。

最大堆Impl：

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++;
}

}

测试类：

    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]);
        }
    }

}

score 0 · Accepted Answer

要解决上面的答案，当前不等于 0，而是堆的大小（带有值）。

int getParent(int index){                                 
    return (index - 1)/2;                                 
}                                 
                                  
void insertHeap(Array tab){                               
    int current = tab.size() -1;                                  
    int i = current;                                  
    int tmp;                                  
    int parent;                               
    while(i > 0) {                                
        parent = getParent(i);                                
        if(tab[parent] < tab[i]) {                                
            tmp = tab[parent];                                
            tab[parent] = tab[i];                                 
            tab[i] = tmp;                                 
        } else break;                                 
        i = parent;                               
    }                                 
    current++;                                
}

java - 将项目插入最大堆

2 回答 2

Related

Reference