Heap
Heap is a tree-based data structure in which all the nodes of the tree are in a specific order. Heap is a complete binary tree-based data structure. Heaps have specific ordering properties. The ordering can be one of two types:
- Max-Heap: The value of a node must be greater than or equal to the values of its children. The greatest value is at the root. The same property must be true for all subtrees.
35 33 42 10 14 19 27 44 26 31
Max-Heap construction
Max-Heap deletion
@NoArgsConstructor @AllArgsConstructor @Data @ToString public class MaxHeap { private List<Integer> data = new ArrayList<>(); /** * Function to return the position of the parent for the node currently at position */ private int parent(int position) { if (position == 0) { return 0; } return (position - 1) / 2; } /** * Function to return the position of the left child for the node currently at position */ private int left(int position) { return (2 * position) + 1; } /** * Function to return the position of the right child for the node currently at position */ private int right(int position) { return (2 * position) + 2; } private void swap(int firstPosition, int secondPosition) { System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition)); int tmp = this.data.get(firstPosition); this.data.set(firstPosition, this.data.get(secondPosition)); this.data.set(secondPosition, tmp); System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition)); } public void add(int item) { this.data.add(item); // increase the size of an array Heap[++size] = element; int current = getSize() - 1; System.out.println("adding: " + item + " to position: " + current); heapifyUp(current); } public int peek() { return data.get(0); } /** * Step 1 − Remove root node.<br> * Step 2 − Move the last element of last level to root.<br> * Step 3 − Compare the value of this child node with its parent.<br> * Step 4 − If value of parent is less than child, then swap them.<br> * Step 5 − Repeat step 3 & 4 until Heap property holds.<br> */ public int poll() { int head = data.get(0); // replace the root of the heap with the last element data.set(0, this.data.get(getSize() - 1)); data.remove(getSize() - 1); // call heapify-down on the root node heapifyDown(0); return head; } /** * Step 1 − Create a new node at the end of heap.<br> * Step 2 − Assign new value to the node.<br> * Step 3 − Compare the value of this child node with its parent.<br> * Step 4 − If value of parent is less than child, then swap them.<br> * Step 5 − Repeat step 3 & 4 until Heap property holds.<br> */ private void heapifyUp(int position) { int temp = this.data.get(position); if (position > 0 && temp > this.data.get(parent(position))) { System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position))); // swap the two if heap property is violated swap(position, parent(position)); // call heapify-up on the parent heapifyUp(parent(position)); } } /** * Step 1 − Remove root node.<br> * Step 2 − Move the last element of last level to root.<br> * Step 3 − Compare the value of this child node with its parent.<br> * Step 4 − If value of parent is less than child, then swap them.<br> * Step 5 − Repeat step 3 & 4 until Heap property holds.<br> */ private void heapifyDown(int position) { int largest = position; int leftChild = left(position); int rightChild = right(position); // compare `A[i]` with its left and right child // and find the largest value int size = getSize(); if (leftChild < size && this.data.get(leftChild) > this.data.get(largest)) { largest = leftChild; } if (rightChild < size && this.data.get(rightChild) > this.data.get(largest)) { largest = rightChild; } if (largest != position) { // swap with a child having lesser value swap(position, largest); // call heapify-down on the child heapifyDown(largest); } } public void print() { System.out.println("\nList"); for (Integer d : data) { System.out.println("data: " + d); } System.out.println("\nTree"); System.out.println("Root: " + data.get(0)); for (int i = 1; i <= getSize() / 2; i++) { try { System.out.print("Parent: " + this.data.get(i - 1)); } catch (Exception e) { } try { System.out.print(", Left: " + this.data.get(this.left(i - 1))); } catch (Exception e) { } try { System.out.print(", Right: " + this.data.get((this.right(i - 1)))); } catch (Exception e) { } System.out.println(); } System.out.println("\n"); } public int getSize() { return this.data.size(); } } - Min-Heap: The value of a node is greater than or equal to the value of its parent. The smallest value is at the root. The same property must be true for all subtrees.
35 33 42 10 14 19 27 44 26 31
@NoArgsConstructor
@AllArgsConstructor
@Data
@ToString
public class MinHeap {
private List<Integer> data = new ArrayList<>();
/**
* Function to return the position of the parent for the node currently at position
*/
private int parent(int position) {
if (position == 0) {
return 0;
}
return (position - 1) / 2;
}
/**
* Function to return the position of the left child for the node currently at position
*/
private int left(int position) {
return (2 * position) + 1;
}
/**
* Function to return the position of the right child for the node currently at position
*/
private int right(int position) {
return (2 * position) + 2;
}
private void swap(int firstPosition, int secondPosition) {
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
int tmp = this.data.get(firstPosition);
this.data.set(firstPosition, this.data.get(secondPosition));
this.data.set(secondPosition, tmp);
System.out.println("firstPosition: " + firstPosition + ", data: " + this.data.get(firstPosition) + ", secondPosition: " + secondPosition + ", data: " + this.data.get(secondPosition));
}
public void add(int item) {
this.data.add(item);
// increase the size of an array Heap[++size] = element;
int current = getSize() - 1;
System.out.println("adding: " + item + " to position: " + current);
heapifyUp(current);
}
public int peek() {
return data.get(0);
}
public int poll() {
int head = data.get(0);
// replace the root of the heap with the last element
data.set(0, this.data.get(getSize() - 1));
data.remove(getSize() - 1);
// call heapify-down on the root node
heapifyDown(0);
return head;
}
/**
* Step 1 − Create a new node at the end of heap.<br>
* Step 2 − Assign new value to the node.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is greater than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyUp(int position) {
int temp = this.data.get(position);
if (position > 0 && temp < this.data.get(parent(position))) {
System.out.println("heapifyUp - position: " + position + ", data: " + this.data.get(parent(position)));
// swap the two if heap property is violated
swap(position, parent(position));
// call heapify-up on the parent
heapifyUp(parent(position));
}
}
/**
* Step 1 − Remove root node.<br>
* Step 2 − Move the last element of last level to root.<br>
* Step 3 − Compare the value of this child node with its parent.<br>
* Step 4 − If value of parent is greater than child, then swap them.<br>
* Step 5 − Repeat step 3 & 4 until Heap property holds.<br>
*/
private void heapifyDown(int position) {
int smallest = position;
int leftChild = left(position);
int rightChild = right(position);
// compare `A[i]` with its left and right child
// and find the smallest value
int size = getSize();
if (leftChild < size && this.data.get(leftChild) < this.data.get(smallest)) {
smallest = leftChild;
}
if (rightChild < size && this.data.get(rightChild) < this.data.get(smallest)) {
smallest = rightChild;
}
if (smallest != position) {
// swap with a child having lesser value
swap(position, smallest);
// call heapify-down on the child
heapifyDown(smallest);
}
}
public void print() {
System.out.println("\nList");
for (Integer d : data) {
System.out.println("data: " + d);
}
System.out.println("\nTree");
System.out.println("Root: " + data.get(0));
for (int i = 1; i <= getSize() / 2; i++) {
try {
System.out.print("Parent: " + this.data.get(i - 1));
} catch (Exception e) {
}
try {
System.out.print(", Left: " + this.data.get(this.left(i - 1)));
} catch (Exception e) {
}
try {
System.out.print(", Right: " + this.data.get((this.right(i - 1))));
} catch (Exception e) {
}
System.out.println();
}
System.out.println("\n");
}
public int getSize() {
return this.data.size();
}
}
Heap Data Structure Applications
- Heap is used while implementing a priority queue.
- Dijkstra’s Algorithm
- Heap Sort
CSS Introduction
CSS (Cascading Style Sheets) is used to style and lay out web pages — for example, to alter the font, color, size, and spacing of your content, split it into multiple columns, or add animations and other decorative features. It is a simple design language intended to simplify the process of making web pages presentable.
CSS handles the look and feel part of a web page. Using CSS, you can control the color of the text, the style of fonts, the spacing between paragraphs, how columns are sized and laid out, what background images or colors are used, layout designs,variations in display for different devices and screen sizes as well as a variety of other effects.
CSS is easy to learn and understand but it provides powerful control over the presentation of an HTML document. Most commonly, CSS is combined with the markup languages HTML or XHTML.
Advantages of CSS
- CSS saves time − You can write CSS once and then reuse same sheet in multiple HTML pages. You can define a style for each HTML element and apply it to as many Web pages as you want.
- Pages load faster − If you are using CSS, you do not need to write HTML tag attributes every time. Just write one CSS rule of a tag and apply it to all the occurrences of that tag. So less code means faster download times.
- Easy maintenance − To make a global change, simply change the style, and all elements in all the web pages will be updated automatically.
- Superior styles to HTML − CSS has a much wider array of attributes than HTML, so you can give a far better look to your HTML page in comparison to HTML attributes.
- Multiple Device Compatibility − Style sheets allow content to be optimized for more than one type of device. By using the same HTML document, different versions of a website can be presented for handheld devices such as PDAs and cell phones or for printing.
- Global web standards − Now HTML attributes are being deprecated and it is being recommended to use CSS. So its a good idea to start using CSS in all the HTML pages to make them compatible to future browsers.
How does CSS work?
When a browser displays a document, it must combine the document’s content with its style information. It processes the document in a number of stages, which we’ve listed below. Bear in mind that this is a very simplified version of what happens when a browser loads a webpage, and that different browsers will handle the process in different ways. But this is roughly what happens.
- The browser loads the HTML (e.g. receives it from the network).
- It converts the HTML into a DOM (Document Object Model). The DOM represents the document in the computer’s memory. The DOM is explained in a bit more detail in the next section.
- The browser then fetches most of the resources that are linked to by the HTML document, such as embedded images and videos … and linked CSS! JavaScript is handled a bit later on in the process, and we won’t talk about it here to keep things simpler.
- The browser parses the fetched CSS, and sorts the different rules by their selector types into different “buckets”, e.g. element, class, ID, and so on. Based on the selectors it finds, it works out which rules should be applied to which nodes in the DOM, and attaches style to them as required (this intermediate step is called a render tree).
- The render tree is laid out in the structure it should appear in after the rules have been applied to it.
- The visual display of the page is shown on the screen (this stage is called painting).
What happens if CSS has an error?
The answer is that it does nothing, and just moves on to the next bit of CSS!
If a browser is parsing your rules, and encounters a property or value that it doesn’t understand, it ignores it and moves on to the next declaration. It will do this if you have made an error and misspelled a property or value, or if the property or value is just too new and the browser doesn’t yet support it.
Similarly, if a browser encounters a selector that it doesn’t understand, it will just ignore the whole rule and move on to the next one.
Git branch
List all branches within a repository
git branch //or git branch --list
List all of remote branches
git branch -a
Create a local branch
git branch {branch-name}
Example: create a branch name test-100
git branch test-100
Check for the new created branch
folaukaveinga@Folaus-MacBook-Pro-3 demo % git branch develop master test-100
Push new local branch to remote
git push --set-upstream origin {branch-name}
Delete local branch
Use -d for safe delete. This means that if there are changes or commits in the branch that have not been commited or pushed up to remote, delete won’t work.
git branch -d {branch-name}
Use -D to force delete the specified branch, even if it has unmerged changes.
git branch -D {branch-name}
Delete a remote branch
git push origin --delete {branch-name}
Rename a branch locally
if you want to rename the branch remotely, Use push origin to reflect the change remotely.
git branch -m {new-branch-name}
Pull a remote branch to local
When you want to pull a remote branch to your local.
git pull origin {remote-branch-name}
// and
git checkout {remote-branch-name}
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);