First answer will be rated the best, thank you for your help. How many calls of
ID: 664687 • Letter: F
Question
First answer will be rated the best, thank you for your help.
How many calls of Trickledown must be made to heapify the following array x? Show array x after each of the Trickledown call. i01 2 34 5 6 7 8 X[i]15 30 2331 40 27751 16Explanation / Answer
public class AdiBinaryHeap { private static class AdiBinaryHeapNode { public E e; public int nodeIndex; public AdiBinaryHeapNode(int index, E e) { this.nodeIndex = index; this.e = e; } } private boolean minHeap; private AdiDynamicArray heapArray; public AdiBinaryHeap() { heapArray = new AdiDynamicArray(); minHeap = true; } public AdiBinaryHeap(int initCap) { heapArray = new AdiDynamicArray(initCap); minHeap = true; } public AdiBinaryHeap(int initCap, boolean isMinHeap) { heapArray = new AdiDynamicArray(initCap); minHeap = isMinHeap; } public int getSize() { return heapArray.getSize(); } private AdiBinaryHeapNode getLeft(AdiBinaryHeapNode p) { return 2*p.nodeIndex+1>=heapArray.getSize()?null:heapArray.get(2*p.nodeIndex+1); } private AdiBinaryHeapNode getRight(AdiBinaryHeapNode p) { return 2*p.nodeIndex+2>=heapArray.getSize()?null:heapArray.get(2*p.nodeIndex+2); } private AdiBinaryHeapNode getParent(AdiBinaryHeapNode n) { if (n == heapArray.get(0)) { return null; } return n.nodeIndex%2==0?heapArray.get((n.nodeIndex-2)/2):heapArray.get((n.nodeIndex-1)/2); } private void switchNodes(AdiBinaryHeapNode a, AdiBinaryHeapNode b) { heapArray.set(a.nodeIndex,b); heapArray.set(b.nodeIndex,a); int c_nodeIndex = a.nodeIndex; a.nodeIndex = b.nodeIndex; b.nodeIndex = c_nodeIndex; } private int compareNodes(AdiBinaryHeapNode a, AdiBinaryHeapNode b) { return minHeap?a.e.compareTo(b.e):b.e.compareTo(a.e); } public E get() { return heapArray.get(0).e; } public void insert(E e) { if (heapArray.getSize() == 0) { heapArray.insert(new AdiBinaryHeapNode(0,e)); return; } AdiBinaryHeapNode toBeInserted = new AdiBinaryHeapNode(heapArray.getSize(),e); heapArray.insert(toBeInserted); while (getParent(toBeInserted) != null && compareNodes(toBeInserted,getParent(toBeInserted))0) { switchNodes(trickleDown,getRight(trickleDown)); } return; } if (getLeft(trickleDown) != null && getRight(trickleDown) == null) { if (compareNodes(trickleDown,getLeft(trickleDown))>0) { switchNodes(trickleDown,getLeft(trickleDown)); } return; } if (compareNodes(getLeft(trickleDown),getRight(trickleDown))0) { switchNodes(trickleDown,getLeft(trickleDown)); } else { return; } } else { if (compareNodes(trickleDown,getRight(trickleDown))>0) { switchNodes(trickleDown,getRight(trickleDown)); } else { return; } } } } }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.