将项目插入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;
}
}
任何帮助将不胜感激。谢谢!
答
你的课堂设计看起来不错。 在堆:
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]);
}
}
}