Write a class that implements a 5-Heap ? c or c++ or java

Question

Hi

I need a formal help of this as i'm a c# coder and i dont know how to do this in other lang's

Write a class (or a set of functions, if you are using C) that implements a 5-Heap (i.e., each node has up to 5 children) using an array as discussed in class. Each node of the heap contains two elements: a priority level (integer), and a string value.

Implement insert(priority, string_value) that inserts an element in the heap, and delete_max() that removes the value with the highest priority and returns the corresponding string value. (Do not implement delete_min). Since delete_min is not required, optimize the heap structure for delete_max. Write a program that inserts 1,000 random elements in your 5-Heap, and then outputs them from the highest priority value to the lowest using delete_max(). (The heap will be empty at the end of the program.) Output only the result of delete_max(), one element at a time, such as:

681469 "element 1"

529834 "element 2"

...

I have no clue were to start and any help is dearly appreciated .

PS: can be done by anyone of these c , c++ , java .

Thanks & Regards

Vulpes · Answer

OK I've done something for you using java. This is based on the implementation of the more general d-ary heap of ints here: http://www.nada.kth.se/kurser/kth/2D1340/inda00/hw0012s.html though I've specialized it to only implement a 5-heap of Element objects. As I wasn't keen on some of the method names I've altered them to be more java-like. The code seems to be working fine: /* FiveHeap.java */ import java.util.Arrays; public class FiveHeap { private Element data[]; private int size; public FiveHeap(int capacity) { data = new Element[capacity]; this.size = 0; } private int getChildIndex(int parentIndex int childNum) { return 5 * parentIndex + childNum + 1; } private int getParentIndex(int childIndex) { return (childIndex - 1) / 5; } public Element getMax() { return data[0]; } public int getSize() { return size; } public void print() { for (int i = 0; i { System.out.println(data[i].getPriority() +  :  + data[i].getValue()); } } public void insert(int priority String value) { if (size == data.length) { System.out.println(Heap is full); return; } Element e = new Element(priority value); data[size] = e; size++; heapUp(size - 1); } public Element deleteMax() { if (size == 0) { System.out.println(Heap is empty); return null; } Element maxValue = getMax(); int currNode = 0; while (getChildIndex(currNode 0) { int maxValuedChild = getChildIndex(currNode 0); int currChild = maxValuedChild; int lastChild = getChildIndex(currNode 5); if (lastChild > size) { lastChild = size; } while (currChild { if (data[currChild].getPriority() > data[maxValuedChild].getPriority()) { maxValuedChild = currChild; } currChild++; } data[currNode] = data[maxValuedChild]; currNode = maxValuedChild; } data[currNode] = data[size - 1]; size--; if (currNode { heapUp(currNode); } return maxValue; } public void heapUp (int startNode) { int currNode = startNode; while(currNode != 0) { if (data[currNode].getPriority() > data[getParentIndex(currNode)].getPriority()) { Element temp = data[currNode]; data[currNode] = data[getParentIndex(currNode)]; data[getParentIndex(currNode)] = temp; currNode = getParentIndex(currNode); } else { break; } } } } class Element { private int priority; private String value; public int getPriority() { return priority; } public String getValue() { return value; } public Element(int priority String value) { this.priority = priority; this.value = value; } } /* FiveHeapTest.java */ import java.io.*; import java.util.*; public class FiveHeapTest { public static void main(String[] args) throws IOException { Random rand = new Random(); FiveHeap heap = new FiveHeap(1000); int min = 100000; int max = 999999; // add 1000 random elements for(int i = 0; i { int num = rand.nextInt((max - min) + 1) + min; // 6 digits String val = Element  + i; heap.insert(num val); } System.out.println(The size of the heap after insertions is  + heap.getSize()); System.out.println(
***** Now press enter key to delete them all *****
); System.in.read(); // now delete them all Element e; for(int i = 0; i { e = heap.deleteMax(); System.out.println(e.getPriority() +  \ + e.getValue() + \); } System.out.println(
The size of the heap after deletions is  + heap.getSize()); } }

SUNIL GUTTA · Answer

Tried something like this in c++ but stuck somewhere unable to way out . And thank you for your great insight using java . Much appreciated . Link to code :- http://ideone.com/kTCXuf#stdin Thank you My friend