In Java Design a linear-time certification algorithm to check whether an array p

Question

In Java Design a linear-time certification algorithm to check whether an array pq is a min-oriented heap using

public static boolean isMinOrientedHeap(int[] a)

which returns true if input array is a minheap and false if it doesn't not.

Thank you!

Explanation / Answer

import java.util.Comparator; import java.util.Iterator; import java.util.NoSuchElementException; /** * The MinPQ class represents a priority queue of generic keys. * It supports the usual insert and delete-the-minimum * operations, along with methods for peeking at the minimum key, * testing if the priority queue is empty, and iterating through * the keys. *

* This implementation uses a binary heap. * The insert and delete-the-minimum operations take * logarithmic amortized time. * The min, size, and is-empty operations take constant time. * Construction takes time proportional to the specified capacity or the number of * items used to initialize the data structure. *

* For additional documentation, see Section 2.4 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class MinPQ implements Iterable { private Key[] pq; // store items at indices 1 to N private int N; // number of items on priority queue private Comparator comparator; // optional comparator /** * Initializes an empty priority queue with the given initial capacity. * @param initCapacity the initial capacity of the priority queue */ public MinPQ(int initCapacity) { pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue. */ public MinPQ() { this(1); } /** * Initializes an empty priority queue with the given initial capacity, * using the given comparator. * @param initCapacity the initial capacity of the priority queue * @param comparator the order to use when comparing keys */ public MinPQ(int initCapacity, Comparator comparator) { this.comparator = comparator; pq = (Key[]) new Object[initCapacity + 1]; N = 0; } /** * Initializes an empty priority queue using the given comparator. * @param comparator the order to use when comparing keys */ public MinPQ(Comparator comparator) { this(1, comparator); } /** * Initializes a priority queue from the array of keys. * Takes time proportional to the number of keys, using sink-based heap construction. * @param keys the array of keys */ public MinPQ(Key[] keys) { N = keys.length; pq = (Key[]) new Object[keys.length + 1]; for (int i = 0; i = 1; k--) sink(k); assert isMinHeap(); } /** * Is the priority queue empty? * @return true if the priority queue is empty; false otherwise */ public boolean isEmpty() { return N == 0; } /** * Returns the number of keys on the priority queue. * @return the number of keys on the priority queue */ public int size() { return N; } /** * Returns a smallest key on the priority queue. * @return a smallest key on the priority queue * @throws java.util.NoSuchElementException if priority queue is empty */ public Key min() { if (isEmpty()) throw new NoSuchElementException("Priority queue underflow"); return pq[1]; } // helper function to double the size of the heap array private void resize(int capacity) { assert capacity > N; Key[] temp = (Key[]) new Object[capacity]; for (int i = 1; i 0) && (N == (pq.length - 1) / 4)) resize(pq.length / 2); assert isMinHeap(); return min; } /*********************************************************************** * Helper functions to restore the heap invariant. **********************************************************************/ private void swim(int k) { while (k > 1 && greater(k/2, k)) { exch(k, k/2); k = k/2; } } private void sink(int k) { while (2*k 0; } } private void exch(int i, int j) { Key swap = pq[i]; pq[i] = pq[j]; pq[j] = swap; } // is pq[1..N] a min heap? private boolean isMinHeap() { return isMinHeap(1); } // is subtree of pq[1..N] rooted at k a min heap? private boolean isMinHeap(int k) { if (k > N) return true; int left = 2*k, right = 2*k + 1; if (left

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.