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

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

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 < size; 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) < size)

{

int maxValuedChild = getChildIndex(currNode, 0);

int currChild = maxValuedChild;

int lastChild = getChildIndex(currNode, 5);

if (lastChild > size)

{

lastChild = size;

}

while (currChild < lastChild)

{

if (data[currChild].getPriority() > data[maxValuedChild].getPriority())

{

maxValuedChild = currChild;

}

currChild++;

}

data[currNode] = data[maxValuedChild];

currNode = maxValuedChild;

}

data[currNode] = data[size - 1];

size--;

if (currNode < size)

{

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 < 1000; 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("\n***** Now press enter key to delete them all *****\n");

System.in.read();

// now delete them all

Element e;

for(int i = 0; i < 1000; i++)

{

e = heap.deleteMax();

System.out.println(e.getPriority() + " \"" + e.getValue() + "\"");

}

System.out.println("\nThe size of the heap after deletions is " + heap.getSize());

}

2 Replies

Know the answer? Post it — somebody with the same question will find it here.

Vulpes12y ago
Accepted 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 < size; 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) < size)
{
int maxValuedChild = getChildIndex(currNode, 0);
int currChild = maxValuedChild;
int lastChild = getChildIndex(currNode, 5);

if (lastChild > size)
{
lastChild = size;
}

while (currChild < lastChild)
{
if (data[currChild].getPriority() > data[maxValuedChild].getPriority())
{
maxValuedChild = currChild;
}

currChild++;
}

data[currNode] = data[maxValuedChild];
currNode = maxValuedChild;
}

data[currNode] = data[size - 1];
size--;

if (currNode < size)
{
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 < 1000; 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("\n***** Now press enter key to delete them all *****\n");
System.in.read();

// now delete them all
Element e;

for(int i = 0; i < 1000; i++)
{
e = heap.deleteMax();
System.out.println(e.getPriority() + " \"" + e.getValue() + "\"");
}

System.out.println("\nThe size of the heap after deletions is " + heap.getSize());
}
}
SUNIL GUTTA11y ago
1. 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