Priority Queue Implementation Using Heap / BST
Dec 4, 2014
I am in the process of implementing Priority queue, as I understand that there are many data structures you could use to implement. I implemented it with the an array, which it works absolutely fine. However I have limitations on what collections I can use from the collections classes. I fact I cant use any of the collections classes. Meaning I cant use array.
I’m trying to implement Priority Queue using heap. And implementing heap using binary trees. But however I have a few questions which I need to clarify and I cant think of any other way of resolving it. Ofcourse I can implement my own simple array class using linked list.
Inserting into heap would be quite simple, as I just need to find the right last position from left to right leaf to insert the node into the tree. However after inserting, you may want to make sure that leaf node values are > than root node. Therefore, the root node will always be with the highest priority.
I call these steps where you compare from top down as bubbledown and bubbleup. To do this I really need a for each node within the treee node to have attribute pointing to its root node. So in case of bubbleup I always have a pointer for a given node to its root, without it would mean I would to traverse through the entire tree to identify its root. Which I believe is very inefficient.
Or have I taken this completely wrong? Or is it the case that heap are only best with arrays and therefore use array (by implement it using linked list?)
View Replies
ADVERTISEMENT
Apr 15, 2014
Implement a priority queue based on a sorted linked list. The remove operation on the priority queue should remove the item with the smallest key.
View Replies
View Related
Nov 28, 2014
I have a class "ExecuteJob" which has Print Q in the form of Priority Q.
You can keep adding job to the Q by calling one of the method in the class. However, and object cant do things simultaneity can it? While im adding a new job to the print queue, can it be executing and existing job in the print Q.
To achieve that, I would need to implement process and threads? I believe am I right? So that adding a job is independent to being removed?
View Replies
View Related
Mar 30, 2014
I have a PriorityQueue called incoming, containing objects of type Vehicle.
All vehicles have a fuel level, that can be accessed by the getter method getFuelLevel().
I want to be able to choose to sort the queue so that the Vehicles with the lowest fuel levels are at the front of the queue.
View Replies
View Related
May 4, 2014
I'm working on a lab for my class. I need to create a Priority Queue in Java using an array list. The kicker is that each node has to have a "handle" which is just an object which contains the index of of the node that it's associated with. I know that sounds weird but we have to implement it this way. Anyway, my priority queue seem to work fine except the handle values apparently aren't updating correctly because I fail the handle test. Also, I run into problems with handles only after extractMin() is called, so I figured the problem would be somewhere in that method but I've been through it a million times and it looks good to me.
Here is my Priority Queue Class:
package lab3;
import java.util.ArrayList;
/**
* A priority queue class supporting operations needed for
* Dijkstra's algorithm.
*/
class PriorityQueue<T> {
final static int INF = 1000000000;
ArrayList<PQNode<T>> queue;
[Code] ....
I can post the tests too but I don't know if that would do much good. Just know that the queue works as is should, but the handles don't point to the right nodes after extractMin() is utilized.
View Replies
View Related
Oct 9, 2014
My assignment was to create a priority queue for Airline Passengers. Here is what I have done so far:
//Driver
package priorityqueuestandby;
import java.util.NoSuchElementException;
import javax.swing.JOptionPane;
public class PriorityQueueStandBy {
public static void main(String[] args) {
[Code] .....
So the part that I cant figure out is:
When a standby passenger is to be enqueued into the priority queue, it must be done so that at the moment of each dequeue operation, the item at the head of the queue is the standby passenger with the longest longevity, and also so that passengers with the same longevity are dequeued in a first-come-first-served fashion.
he says that we need to "Make your program so that it extends Comparable and implements the compareTo() method properly..."
So I was looking at the Comparable class and I could't find a compareTo() method... I am not confident I know how extends works either. I am assuming I need a new class if I am going to be extending another class. Right now I am taking in longevity as a String and converting it to an int because my last ditch effort is going to be to set up a loop that will organize longevity into a/an circular array based on the size of the incoming integer.
View Replies
View Related
May 14, 2014
I was given some code by a professor to add some features to as part of an assignment. However, the code itself doesn't seem to work.
import java.util.HashSet;
import java.util.InputMismatchException;
import java.util.PriorityQueue;
import java.util.Scanner;
import java.util.Set;
public class DijkstraPriorityQueue
[Code] ....
The method to find minimum distance is nonfunctional...I receive an error that the types are incompatible. I can't do the assignment if the base code doesn't work to begin with...
View Replies
View Related
Nov 12, 2014
The following codes shows an implementation of an enqueue function of a FIFO immutable queue, and the output result shows the String "c".
I don't understand why since I expected it should be null.
The head and the tail of an ImmutableQueue Object are two separate queue, and each time I call the enqueue function, it just return a new object with a new tail, however, the head is not modified except the first two times I call the function.
Therefore, I expected head.next.next should be a null element, but the result is not like that.
public class ImmutableQueue<E> {
private int size =0;
public Queue<E> head;
public Queue<E> tail;
public ImmutableQueue(){}
private ImmutableQueue(Queue<E> hd, Queue<E> tl){
head=hd;
tail=tl;
[Code] ....
View Replies
View Related
Nov 12, 2014
The following codes shows an implementation of an enqueue function of a FIFO immutable queue, and the output result shows the String "c". I don't understand why since I expected it should be null.
The head and the tail of an ImmutableQueue Object are two separate queue, and each time I call the enqueue function, it just return a new object with a new tail, however, the head is not modified except the first two times I call the function.
Therefore, I expected head.next.next should be a null element, but the result is not like that.
public class ImmutableQueue<E> {
public Queue<E> head;
public Queue<E> tail;
public ImmutableQueue(){}
private ImmutableQueue(Queue<E> hd, Queue<E> tl){
head=hd;
tail=tl;
[Code] ......
View Replies
View Related
Feb 21, 2014
So I have 3 classes in this project, and When it compiles, I get a null pointer.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
public class Project2 {
[Code] .....
View Replies
View Related
Feb 1, 2014
I have an assignment to complete where I have to develop a Java Console application in Eclipse which accepts regional zone information for premises based upon addresses provided. The program needs to figure out which geographical zone each customer lives in and based upon their age, set a priority rating.
The zones (which is the Belfast and the directions) and sub-zones (which are the Postcode such as "BT1" are:
Zones
BELFAST
"BT1 ", "BT2 ", "BT3 ", "BT4 ", "BT5 ", "BT6 ", "BT7 ", "BT8 ", "BT9 ", "BT10", "BT11", "BT12", "BT13", "BT14", "BT15"
NORTH
"BT39", "BT40", "BT41", "BT42", "BT43", "BT44", "BT45", "BT46", "BT51", "BT52", "BT53", "BT54", "BT55", "BT56", "BT57"
SOUTH
"BT25", "BT26", "BT32", "BT35", "BT60", "BT61", "BT62", "BT63", "BT64", "BT65", "BT66", "BT67", "BT68", "BT69", "BT70", "BT71", "BT80"
EAST
"BT16", "BT17", "BT18", "BT19", "BT20", "BT21", "BT22", "BT23", "BT24", "BT27", "BT28", "BT29", "BT30", "BT31", "BT33", "BT34", "BT36", "BT37", "BT38"
WEST
"BT47", "BT48", "BT49", "BT74", "BT75", "BT76", "BT77", "BT78", "BT79", "BT81", "BT82", "BT92", "BT93", "BT94"
UNALLOCATED
No Postcode provided
What I specifically need to do is
1.Display a count of addresses within a user defined geographical zone.
2.Display all information for customers within a user defined geographical zone.
3.Display a complete set of captured data.
4.Display a prioritized list of customer details within each geographical zone.
5.Display a count of customers within each geographical zone.
Below is the code I have created so far for it.
package assignment1;
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Assignment1 {
private static InputStreamReader input = new InputStreamReader(System.in);
private static BufferedReader reader = new BufferedReader(input);
[Code] .....
The main issue I'm having is to make sure that data like address and customer counts, and customer details appear only for the selected areas.
View Replies
View Related
Sep 25, 2014
When I add an element to my array, I have to make sure that it stays a heap, ie every child is smaller than its parent. However the method that I am using for this, trickling up, is not updating the elements properly, it pretty much just leaves is as is.
Here is the relevant code:
public class MaxIntHeap {
int[] array;
int actualSize = 0;
public MaxIntHeap(){
array = new int[20];
[code].....
View Replies
View Related
Nov 25, 2014
in my class is implement a heap and use some of the methods we were provided. The methods I was provided to code and use are "siftDown", "isEmpty" and "heapify". I'm pretty sure the code I have written for "heapify" and "isEmpty" is correct, where I think I am finding fault is the code for my "siftDown". Would you mind taking a look at my code and see why when adding integers to the heap object that I have created in the main code, that they are not being output correctly?
public class Tester {
public static void main(String[] args) {
Heap myHeap = new Heap();
myHeap.insert(9);
myHeap.insert(15);
myHeap.insert(6);
myHeap.insert(4);
myHeap.insert(10);
myHeap.insert(9);
myHeap.insert(3);
[code]....
View Replies
View Related
Jul 3, 2014
maximum heap size is set at 1.5GB and consumption of memory at peak load is about 1.1GB. when it reaches 1.1GB, application starts to hang. what could be the problem? shouldn't it be hanging at the point where memory is about equal to the max heap setting? no heap dumps were generated. is this due to server hardware or something? already got the garbage collection data and nothing seemed unusual.
View Replies
View Related
May 5, 2015
I am learning to use heaps and as an exercise I am trying to write a program using a heap class I have created to sort words. I have read in words from a file and added them to the heap successfully. I am having some trouble figuring out how I can print out a sorted list of the words. From my understanding of how a min-heap works, if I remove from the min/root node they will always be removed in sorted order. So far I have tried out to do a simple for loop but, only half of the heap is being removed. Not sure if my logic is incorrect of there is an error somewhere in my removeMin() function specifically in the while loop.
public static void main(String[] args) {
Heap heap = new Heap();
heap = read( heap );
for( int i = 0; i < heap.getSize(); i++){
heap.removeMin();
[Code] ....
View Replies
View Related
Nov 10, 2013
What is the ratio of Memory(RAM) to heap space ? ie: When JVM will throw OutOfMemoryError based on heap available to JVM ?
OutofMemoryError - Memory:RAM size
View Replies
View Related
Nov 21, 2013
I am using a 64 bit Win 7 Pc with 64-bit JVM and we get the error: Java heap space. So we want to increase the Java heap size but not for one application but for every application or in general.
We tried with the java -xmx command but it didn't work...
We tried setting the system variable JAVA_OPTS but again it didn't work...
View Replies
View Related
Dec 16, 2013
I have two unix systems in which on one system I installed sun solaris jdk and on another system I installed IBM jdk.
Java programs which consume more heap memory are getting failed on sun solaris jdk system where as same programs are successfully getting executed on IBM jdk system .
My question is does sun solaris 64 bit jdk needs more heap than IBM 64 bit jdk ??
View Replies
View Related
Sep 29, 2014
When I try to write the .xlsx file using apache POI, XSSFWorkbook API and run this program in Eclipse STS, I am getting the java.lang.OutOfMemoryError: Java heap space error. Then I searched the net and add these -Xms512m -Xmx1024m in the eclipse VM arguments. Even though I am getting the same error. Again i increase heap size but i am getting the different error like "occurred during initialization of VM, Could not reserve enough space for object heap". how to increase the heap size or any other API to read, delete and write the .xlsx file. I am having 4GB ram in my machine. Apache POI is very good for .xls but if it is .xlsx performance wise it is very slow.
View Replies
View Related
Sep 28, 2014
Given a string, compute a new string where identical chars that are adjacent in the original string are separated from each other by a "*". My implementation :
package com.tcs.dash;
public class StringBuild {
public String edit(String userIp){
StringBuilder builder = new StringBuilder(userIp);
String replaceText = "";
for(int i = 0; i < builder.length() - 1; i++){
if(builder.charAt(i) == builder.charAt(i+1)){
replaceText = builder.charAt(i) + "*" + builder.charAt(i+1);
builder = builder.replace(i, i+1, replaceText);
}
}
return builder.toString();
}
}
I am getting error at line 13. An exception actually.
I/P given = aaaa
Console:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOf(Unknown Source)
at java.lang.AbstractStringBuilder.expandCapacity(Unknown Source)
at java.lang.AbstractStringBuilder.ensureCapacityInternal(Unknown Source)
at java.lang.AbstractStringBuilder.replace(Unknown Source)
at java.lang.StringBuilder.replace(Unknown Source)
at com.tcs.dash.StringBuild.edit(StringBuild.java:13)
at com.tcs.dash.StringBuildExample.main(StringBuildExample.java:14)
View Replies
View Related
Apr 9, 2014
I have a simple JavaFX Application that open a Browser and shows google page. After exit the Application and free all objects, I can see that the JavaFX objects like Scene, Stage, WebView and WebEngine are alive in the heap memory after call GC. I can see this objects with JProfiler and other Profiler tools.
This is my Test code:
import java.awt.FlowLayout;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import javafx.application.Application;
import javafx.application.Platform;
[Code] .....
And my JavaFX Application:
import javafx.application.Application;
import javafx.geometry.HPos;
import javafx.geometry.VPos;
import javafx.scene.Scene;
import javafx.scene.layout.Region;import javafx.scene.paint.Color;
[Code] .....
To test the application click on Start Button to show google web page, click on Stop Button to stop the application, run a Profiler tool, and call gc, the JavaFX classes are alive. I am using java version "1.7.0_51" and windows 8.1 Is there something wrong in my code? Or this is the normal behavior?
View Replies
View Related
Jul 7, 2014
I was wondering where is the memory allocated for an applet; by the browser; by the JVM; some applet specific java option? I get an out of memory error when running my applet (loading pictures).
View Replies
View Related
May 4, 2015
Properties info = new Properties( );
info.put( "user", "username" );
info.put( "password", "password" );
Connection conn = DriverManager.getConnection(URL, info);
I am using simple jdbc connection to connect to Sybase as shown above , problem is security team is able to see password as clear text in heap, How to avoid it.
View Replies
View Related
Nov 18, 2014
I am working on program and have been struggling to get around step 5 and 6 given below.
I have got on with the first couple of points. Where to begin with steps 5 and 6.
Java Code:
class Hourglass {
int height;
int bottomHalf;
public Hourglass (int h) {
height =h;
}
public Hourglass (){
height=3;
}
/*Write a method dropGrain that simulates one grain of sand falling into the bottom half of the Hourglass. If all the sand is already at the bottom before a grain is dropped, this method should cause the hourglass to be flipped, meaning that all the sand will be in the top again. Then, one grain of sand should fall. */
//Hint: this method can be quite short. All you need to do is update one attribute.
public void dropGrain(){
}
/*Write a method getHeapHeight() which returns the height of the heap of sand in the bottom of the hourglass.
Hint: a triangle of height h contains h*h grains (=1+3+5+...+h).
So determining the height when the amount of sand in the bottom half is a square (1,4,9,16,...) is easy. Think about what happens if the amount of sand is not exactly a square.*/
public int getHeapHeight() {
} mh_sh_highlight_all('java');
View Replies
View Related
Jun 21, 2014
I am not a java developer, but I am using a java code that was available online to convert a large XML file to CSV file. The input file size is big, it is around 3GB. I got an error that it is out of memory, it is expectedly due to the large input file that i am trying to convert. Splitting of this file is not possible,
This is what I ran : xml2csv-conv data.xml data.csv
Error:
Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at com.sun.org.apache.xerces.internal.dom.DeferredDoc umentImpl.createChunk(Unknown Source)
at com.sun.org.apache.xerces.internal.dom.DeferredDoc umentImpl.ensureCapacity(Unknown Source)
at com.sun.org.apache.xerces.internal.dom.DeferredDoc umentImpl.createNode(Unknown Source)
at com.sun.org.apache.xerces.internal.dom.DeferredDoc umentImpl.createDeferredTextNode(Unknown Source)
at com.sun.org.apache.xerces.internal.parsers.Abstrac tDOMParser.character
[code]....
Additional information: I am running this from a Windows8 64 bit machine with 8GB physical RAM.
View Replies
View Related
Mar 6, 2014
i have to write more than 100000 rows in a excel sheet (file size more than 20 MB) via java.
when i use XSSF, i am getting below Error.
java.lang.OutOfMemoryError: Java heap space
at org.apache.xmlbeans.impl.store.Saver$TextSaver.resize(Saver.java:1592)
at org.apache.xmlbeans.impl.store.Saver$TextSaver.preEmit(Saver.java:1223)
at org.apache.xmlbeans.impl.store.Saver$TextSaver.emit(Saver.java:1144)
[Code]....
when i use HSSF , i am getting the below Error.
java.lang.OutOfMemoryError: Java heap space
I have tried increasing the java heap size , by giving upto -Xms1500m -Xmx2048m
View Replies
View Related
