This here -----> http://practiceit.cs.washington.edu in the 3rd edition chapter
ID: 3677057 • Letter: T
Question
This here -----> http://practiceit.cs.washington.edu
in the 3rd edition
chapter 18 problem number 15
Write a method in the HeapIntPriorityQueue class called merge that accepts another HeapIntPriorityQueue as a parameter and adds all elements from the other queue into the current queue, maintaining proper heap order such that the elements will still come out in ascending order when they are removed. Your code should not modify the queue passed in as a parameter. (Recall that objects of the same class can access each other's private fields.)
Related Files:
Explanation / Answer
import java.util.Arrays;
import java.util.NoSuchElementException;
// Implements a priority queue of integers using a
// min-heap represented as an array.
public class HeapIntPriorityQueue {
private int[] elementData;
private int size;
// Constructs an empty queue.
public HeapIntPriorityQueue() {
elementData = new int[10];
size = 0;
}
// Adds the given element to this queue.
public void add(int value) {
// resize if necessary
if (size + 1 >= elementData.length) {
elementData = Arrays.copyOf(elementData, elementData.length * 2);
}
// insert as new rightmost leaf
elementData[size + 1] = value;
// "bubble up" toward root as necessary to fix ordering
int index = size + 1;
boolean found = false; // have we found the proper place yet?
while (!found && hasParent(index)) {
int parent = parent(index);
if (elementData[index] < elementData[parent]) {
swap(elementData, index, parent(index));
index = parent(index);
} else {
found = true; // found proper location; stop the loop
}
}
size++;
}
// Returns true if there are no elements in this queue.
public boolean isEmpty() {
return size == 0;
}
// Returns the minimum value in the queue without modifying the queue.
// If the queue is empty, throws a NoSuchElementException.
public int peek() {
if (isEmpty()) {
throw new NoSuchElementException();
}
return elementData[1];
}
// Removes and returns the minimum value in the queue.
// If the queue is empty, throws a NoSuchElementException.
public int remove() {
int result = peek();
// move rightmost leaf to become new root
elementData[1] = elementData[size];
size--;
// "bubble down" root as necessary to fix ordering
int index = 1;
boolean found = false; // have we found the proper place yet?
while (!found && hasLeftChild(index)) {
int left = leftChild(index);
int right = rightChild(index);
int child = left;
if (hasRightChild(index) &&
elementData[right] < elementData[left]) {
child = right;
}
if (elementData[index] > elementData[child]) {
swap(elementData, index, child);
index = child;
} else {
found = true; // found proper location; stop the loop
}
}
return result;
}
// Returns the number of elements in the queue.
public int size() {
return size;
}
// Returns a string representation of this queue, such as "[10, 20, 30]";
// The elements are not guaranteed to be listed in sorted order.
public String toString() {
String result = "[";
if (!isEmpty()) {
result += elementData[1];
for (int i = 2; i <= size; i++) {
result += ", " + elementData[i];
}
}
return result + "]";
}
// helpers for navigating indexes up/down the tree
private int parent(int index) {
return index / 2;
}
// returns index of left child of given index
private int leftChild(int index) {
return index * 2;
}
// returns index of right child of given index
private int rightChild(int index) {
return index * 2 + 1;
}
// returns true if the node at the given index has a parent (is not the root)
private boolean hasParent(int index) {
return index > 1;
}
// returns true if the node at the given index has a non-empty left child
private boolean hasLeftChild(int index) {
return leftChild(index) <= size;
}
// returns true if the node at the given index has a non-empty right child
private boolean hasRightChild(int index) {
return rightChild(index) <= size;
}
// switches the values at the two given indexes of the given array
private void swap(int[] a, int index1, int index2) {
int temp = a[index1];
a[index1] = a[index2];
a[index2] = temp;
}
}
HeapMain.java
// This client program tests our priority queue of integers
// by adding and removing several elements from it.
public class HeapMain {
public static void main(String[] args) {
HeapIntPriorityQueue pq = new HeapIntPriorityQueue();
int[] elements = {65, 50, 20, 90, 44, 60, 80, 70, 99, 10};
for (int n : elements) {
pq.add(n);
System.out.println(pq);
}
// System.out.println(pq);
while (!pq.isEmpty()) {
System.out.println(pq.remove());
System.out.println(pq + ", size "+ pq.size());
}
}
}
sample output
[65]
[50, 65]
[20, 65, 50]
[20, 65, 50, 90]
[20, 44, 50, 90, 65]
[20, 44, 50, 90, 65, 60]
[20, 44, 50, 90, 65, 60, 80]
[20, 44, 50, 70, 65, 60, 80, 90]
[20, 44, 50, 70, 65, 60, 80, 90, 99]
[10, 20, 50, 70, 44, 60, 80, 90, 99, 65]
10
[20, 44, 50, 70, 65, 60, 80, 90, 99], size 9
20
[44, 65, 50, 70, 99, 60, 80, 90], size 8
44
[50, 65, 60, 70, 99, 90, 80], size 7
50
[60, 65, 80, 70, 99, 90], size 6
60
[65, 70, 80, 90, 99], size 5
65
[70, 90, 80, 99], size 4
70
[80, 90, 99], size 3
80
[90, 99], size 2
90
[99], size 1
99
[], size 0
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.