Priority Queue
Priority queue is a data structure that extends the queue data structure with a priority dimension. Queue is a list of elements taken in the same order as they arrived. For instance, a line of people waiting to pay at the Supermarket behaves like a queue: first-in, first-served, or FIFO (first in, first out).
Priority queue adds a priority to each element’s value. If we go back to the example of a line of people in a supermarket. You can add preferred lanes, for example, Seniors (65+ years old) and pregnant women. If you have Seniors in the line, you will take them first, even if other people arrived before them. That’s what a priority queue (PQ) does. If all elements in a PQ have the same priority, then it will behave like a regular queue.
Applications of Priority Queue
There are many real-world applications for priority queues, such as:
- System to triage hospital patients and attend them by their severity order.
- Forward network packages in order of urgency (e.g., “real-time video call” should go before “time sync checks,” so to speak)
- Scheduling tasks in a system: “critical” goes before “shadow drawing” for instance.
- Asynchronous control flows like firing events (or notifying observers) in a certain order.
- Keeping track of top k elements efficiently
- Keeping track of median numbers in constant time
- Used in some graph algorithms like Dijkstra for finding the shortest path between two points. The distance among points is used as a priority.
Implementations
- Let’s explore several possibilities for data structures we could use to implement a priority queue:
- Unordered array
A simple, yet inefficient implementation, as retrieving the max element would require searching the entire array.
- Sorted array
This is not a very efficient implementation either. Inserting a new element requires linearly searching the array for the correct position. Removing similarly requires a linear time: the rest of the elements need to be adjusted (shifted) into correct positions.
- Hash table
Although inserting into a hash table takes constant time (given a good hash function), finding the max element takes linear time. Therefore, this would be a poor choice for the underlying data structure.
- Heap
It turns out that that a heap makes an efficient priority queue.
- Unordered array
| Operation | Unordered array | Sorted array | Hash table | Binary heap |
|---|---|---|---|---|
|
insert |
|
|
|
|
|
maxElement |
|
|
|
|
|
removeMaxElement |
|
|
|
|
public class MyPriorityQueueWithArray {
private int count = 0;
private int capacity = 10;
private PriorityNode[] elements = new PriorityNode[capacity];
public void enqueue(PriorityNode node) {
if (node == null || node.getData() == null) {
return;
}
System.out.println("node: " + node.toString());
System.out.println("count: " + count);
int position = 0;
if (count == 0) {
/**
* tail has the highest priority
*/
elements[position] = node;
} else {
PriorityNode highestNode = elements[position];
while (highestNode != null && node.getPriority() <= highestNode.getPriority()) {
position++;
highestNode = elements[position];
}
add(node, position);
}
System.out.println("insert position: " + position);
System.out.println("\n");
count++;
}
private void add(PriorityNode node, int position) {
if (count == capacity) {
/*
* when full, double its size
*/
capacity = capacity * 2;
}
PriorityNode[] temp = new PriorityNode[capacity];
int index = 0;
int lastIndex = count + 1;
while (index < lastIndex) {
if (index < position) {
/**
* front
*/
temp[index] = elements[index];
} else if (index == position) {
/**
* middle
*/
temp[position] = node;
} else {
/**
* back
*/
temp[index] = elements[index - 1];
}
index++;
}
elements = temp;
}
public PriorityNode removeAt(int position) {
PriorityNode[] temp = new PriorityNode[capacity];
PriorityNode removedNode = elements[position];
int index = 0;
int lastIndex = count + 1;
while (index < lastIndex) {
if (index < position) {
/**
* front
*/
System.out.println("front");
temp[index] = elements[index];
} else if (index == position) {
/**
* middle
*/
System.out.println("middle");
} else {
/**
* back
*/
System.out.println("back");
temp[index - 1] = elements[index];
}
if (temp[index] != null)
System.out.println("temp: " + temp[index].toString());
index++;
System.out.println("\n");
}
elements = temp;
return removedNode;
}
/**
* Retrieves, but does not remove, the head of this queue, or returns null if this queue is empty.
*/
public PriorityNode peek() {
return elements[0];
}
/**
* Retrieves and removes the head of this queue, or returns null if this queue is empty.
*/
public PriorityNode dequeue() {
return removeAt(0);
}
public void print() {
int index = 0;
PriorityNode node = elements[0];
while (node != null && count > index) {
System.out.println((index + 1) + ". " + node.toString());
index++;
node = elements[index];
}
}
}
Javascript Timing
Timing
JavaScript code can be executed in time-intervals either by set a timeout and then execute a funciton or set an interval and then execute a function repeatedly.
setTimeout(function, milliseconds)
// wait 3 seconds and then execute function
let timeout = setTimeout(function(){
console.log("timeout!");
}, 3000);
clearTimeout(setTimeout)
/** * clearTimeout * The clearTimeout() method stops the execution of the function specified in setTimeout(). */ // stop timeout from executing. clearTimeout(timeout);
setInterval(function, milliseconds)
/**
* setInterval(function, milliseconds)
* The setInterval() method repeats a given function at every given time-interval.
*
*/
let interval = setInterval(() => {
console.log("fire interval!");
}, 1000);
clearInterval(setInterval)
/**
*
* clearInterval(interval);
*/
setTimeout(() => {
// stom interval after 6 seconds
clearInterval(interval);
}, 6000);
Queue
Queue is an ordered list in which insertions are done at one end (back) and deletions are done at other end (front). The first element to be inserted is the first one to be deleted. Hence, it is called First in First out (FIFO) or Last in Last out (LILO) list.
In general, a queue is a line of people or things waiting to be served in sequential order starting at the beginning of the line or sequence.
When an element is inserted in a queue, the concept is called EnQueue, and when an element is removed from the queue, the concept is called DeQueue. DeQueueing an empty queue is called underflow and EnQueuing an element in a full queue is called overflow.
Basic features of Queue
- Like stack, queue is also an ordered list of elements of similar data types.
- Queue is a FIFO( First in First Out ) structure.
- Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue must be removed, to remove the new element.
peek()function is oftenly used to return the value of first element without dequeuing it.
Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of objects in an order in which the first one coming in, also gets out first while the others wait for their turn, like in the following scenarios:
-
- Serving requests on a single shared resource, like a printer, CPU task scheduling etc.
- Operating systems schedule jobs (with equal priority) in the order of arrival (e.g., a print queue).
- Simulation of real-world queues such as lines at a ticket counter, or any other first- come first-served scenario requires a queue.
- In real life scenario, Call Center phone systems uses Queues to hold people calling them in an order, until a service representative is free.
- Handling of interrupts in real-time systems. The interrupts are handled in the same order as they arrive i.e First come first served.
- Asynchronous data transfer (file IO, pipes, sockets).
- Determining number of cashiers to have at a supermarket.
Time Complexity of Queue Operations
Just like Stack, in case of a Queue too, we know exactly, on which position new element will be added and from where an element will be removed, hence both these operations requires a single step.
- Enqueue: O(1)
- Dequeue: O(1)
- Size: O(1)
Implementations of Queue
Queue can be implemented using an Array, List, or Linked List. LinkedList has the best performance.
@Data
@NoArgsConstructor
public class MyQueue<E> {
private LinkedList<E> list = new LinkedList<>();
public E enqueue(E item) {
list.addFirst(item);
return item;
}
public E dequeue() {
if (list.size() <= 0) {
throw new EmptyStackException();
}
return list.removeLast();
}
public int getSize() {
return list.size();
}
public void print() {
int size = getSize();
int count = 1;
if (count >= size) {
return;
}
E item = list.getFirst();
while (item != null) {
System.out.println(item.toString());
if (count >= size) {
break;
}
item = list.get(count);
count++;
}
}
}
MySQL Server Helpful Functions
Show connections that your MySQL server has
show status like 'Conn%';
show status like '%onn%';
Show all users of your MySQL server
select * from mysql.user;
select host, user, password from mysql.user;
Describe a table
desc user;October 31, 2019
Javascript this keyword
The this keyword references the object of which the function is a property. In other words, the this references the object that is currently calling the function.
When this is used alone, the owner is the Global object, so this refers to the Global object. In a browser window the Global object is the Window object.
this in global object
/*
* Global this
* Alone, this refers to the global object.
*/
var pageName = "This Keyword";
function showPageName(){
console.log("pageName: " + this.pageName);//This Keyword
}
showPageName();
this in a method
JavaScript “strict mode” does not allow default binding. So, when this is used in a function, in strict mode, this is undefined.
/**
* In a method, this refers to the owner object
*/
let person = {
firstName: "John",
lastName : "Doe",
id : 5566,
fullName : function() {// person is the owner of this function
return this.firstName + " " + this.lastName;
}
};
console.log("fullName: "+person.fullName());//John Doe
this in an arrow function
If this is used in an arrow function, this is referencing outer fields or methods.
/*
* this in arrow funciton
* Arrow functions are special: they don’t have their “own” this.
* If we reference this from such a function, it’s taken from the outer “normal” function.
*/
let user = {
name: "Folau",
sayHi() {
//If we reference this from such a function, it’s taken from the outer “normal” function.
let arrow = () => console.log("arrow name: "+this.name);//arrow name: Folau
arrow();
function sayMyName(){
console.log("my name: "+this.name);//my name:
}
sayMyName();
}
};
user.sayHi();