Implement a min-heap, Data Structure & Algorithms

Description

A heap is an efficient tree-based data structure that can be used as a priority queue. Recall that the abstract data type of a priority queue has the following operations

  • size, isEmpty, min
  • insert
  • removeMin

We can describe the priority queue ADT using the following Java Entry class and interface:

1 import java.lang.Comparable;

2

3 /**

4 * When items are added to the heap, you should create an Entry object

5 * to hold the key and value and store this in the appropriate node

6 */

7 public class Entryextends Comparable,V> {

8 protected K key;

9 protected V value;

10 public MyEntry(K k, V v) { key = k; value = v; }

11 public K getKey() { return key; }

12 public V getValue() { return value; }

13 public String toString() { return "(" + key + "," + value + ")"; }

14 }

15

16 public interface PriorityQueueextends Comparable,V> {

17 /** Returns the number of items in the priority queue. */

18 public int size();

19 /** Returns whether the priority queue is empty. */

20 public boolean isEmpty();

21 /** Returns but does not remove an entry with minimum key. */

22 public Entry min();

23 /** Inserts a key-value pair and return the entry created. */

24 public Entry insert(K key, V value);

25 /** Removes and returns an entry with minimum key. */

26 public Entry removeMin();

27 }

 

The main operations (insert, removeMin) can be done in O(log n) with a heap, while the other operations of the priority queue ADT (isEmpty, size, or look up the min value) are constant time. In lectures we have seen how to implement a heap using an array-based implementation.

58_Implement a min-heap.png

Figure 1: 3-way heap example

For this assignment you must implement a min-heap using a using a tree-based implementation (similar to the binary tree class we have used in tutorials). This tree should be 3-way tree, where each node needs to have (at most) three children

Note that the definition of a 3-way heap is identical to that of a binary heap, except for allowing at most three children (see Figure ). As with a binary tree, every node must have all of its children, except for the nodes at the last levels of the tree. In more detail, your task is to

1. Design a 3-way tree structure that you will use for building your heap. You can use code provided in the book. You can use any helper data structures that you need (linked lists, arrays etc.), but you must implement the tree structure yourself.

2. Implement your design for a generic 3-way heap in a class called ThreewayHeap. You will need to implement all operations (insert, removeMin, isEmpty, etc.) in the supplied interface and skeleton for the 3-way heap. In most cases the extension is straightforward from binary heaps, with certain extra cases that you need to check.

3. Include a method in your heap to print out a visual representation in DOT format (helpful for testing/debugging purposes).

4. Design test cases for your new heap structure, used as a priority queue

5. Use the provided test code on your implementation

Posted Date: 2/28/2013 3:10:39 AM | Location : United States







Related Discussions:- Implement a min-heap, Assignment Help, Ask Question on Implement a min-heap, Get Answer, Expert's Help, Implement a min-heap Discussions

Write discussion on Implement a min-heap
Your posts are moderated
Related Questions
The data structure needed to evaluate a postfix expression is  Stack

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Difference among Prism's and Kruskal's Algorithm In Kruskal's algorithm, the set A is a forest. The safe edge added to A is always a least-weight edge in the paragraph that lin

Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

You have to design a framework of a Genetic Algorithm (GA) with basic functionality. The basic functionality includes representation, recombination operators, tness function and se

Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

A depth-first traversal of a tree visits a nodefirst and then recursively visits the subtrees of that node. Similarly, depth-first traversal of a graph visits a vertex and then rec

In this unit, the following four advanced data structures have been practically emphasized. These may be considered as alternative to a height balanced tree, i.e., AVL tree.

What is Access Restrictions Structured containers with access restrictions only allow clients to add, remove and examine elements at certain locations in their structure. For