Heap

Reading Time: 3 minutes

Description

Heap is a tree-based data structure with some special attributes embedded into it.  Heap Data Structure has such characteristics;

  • It is a form of Complete Binary Tree,
  • It has a root node and its key is compared to the children nodes and the comparison is constantly carried out whenever a new node is aimed to be inserted.

In addition to the characteristics, the Heap can be internally implemented using Array or Priority Queues. The common practice is usually done with the Priority Queue.

Types of Heap

Heap Data Structure has mainly two types. These types correspond to how the order of the Heap is placed. Let’s have a look at the types in details;

Min Heap

Min Heap Tree

The values of children are greater than or equal to the value of their parents; which indicates that parent nodes tend to have lower values than the children nodes.

Max Heap


Max Heap Tree

The values of children are less than or equal to the value of their parents; which indicates that parent nodes tend to have greater values than the children nodes.

Complexity of Heap

The Time and Space complexities are summed up into a common table given as:

Usage Areas of Heap

Heap Data Structure makes great use in the following areas:

  1. Heap Sort: Very efficient sorting algorithm whose time complexities are all the same O (n log n),
  2. Priority Queues: The Priority version of Queue benefits efficiently from the Heap Data structure that provides insertion, deletion extract maximum and decrease key operations in the O (log n) time complexity

Terminology

Heapify

Heapifying is a recursive process of turning the Heap to the Max Heap type, our algorithm will go towards the non-leaf nodes and look for the largest node in the tree and in all possibilities, raise the greater values above top contentiously.

Max Heap

Parent Node

Left node of the Tree the presentation in the array: (index -1) / 2;

Left Node

Left node of the Tree the presentation in the array: 2 * index + 1;

Right Node

Right node of the Tree the presentation in the array: 2 * index + 2;

Heap Sort

Heap sort is a very efficient algorithm that performs very well in sorting arrays.

Time Complexity

All the cases are O(n log n)

Space Complexity

O(1)

Heap Sort Code

You can checkout my GitHub repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/SortingAlgorithms

Linked List

Reading Time: 3 minutes

Definition

Linked List a linear data structure like Arrays, but its internal is completely different compared to other data structures. Let’s first have a visual look how the data structure looks like

The internal of Linked List

As you can see in the above image Linked List maintains a list of objects linked to them, as also the name suggests the same approach. To conclude some characteristics in Linked List;

  1. Each node has a next pointer/reference to the next or previous object then we are iterating through these references,
  2. The last nodes are usually null,
  3. However, the next/previous references  do not refer to null in certain times(in the following chapters, I’ll demonstrate the reasons)

Linked list is used in some data structures like Queues and Stacks internally. Check them out separately and see how Linked List fits in their requirements.

Advantages

  1. No size limitation compared to the arrays,
  2. It is not costly to insert and remove in between nodes, where as it is very costly especially with heavier arrays because all the elements will be shifted,

Disadvantages

  1. Random data access is not possible, the whole data structure must be traversed to access the designated object,
  2. Storage to the next and previous nodes takes up some memory space.

Time and Space Complexity

image courtesy of  bigocheatsheet.com

Types of Linked Lists

Linked List has some varieties of implementations that often confuse us. I’ll show all the implementations in sub sections with visuals, descriptions and codes that will let you interact more and apprehend the slightest differences better.

Singly Linked List

In a Singly Linked List the traversal is unidirectional, each node refers to the next node in the link, and there is no reference to previous nodes.  The last node’s next refers to Null.

See the Implementation “SinglyLinkedList.java” and the Unit Test “SinglyLinkedListUnitTest.java” to apprehend all the operations and internals of the Singly Linked List.

Doubly Linked List

Doubly Linked List maintains a bidirectional path, thus it contains next and previous links, where next refers to the next node, and previous refers to the previous node. This maintenance comes with an extra overhead. Last of all, first node’s previous and last node’s next are Null.

See the Implementation “SinglyLinkedList.java” and the Unit Test “DoublyLinkedListUnitTest.java” to apprehend all the operations and internals of the Doubly Linked List.

Circular Linked List

Circular Linked List is the last variation of the implementation. I would like to call the Circular Linked List as the spiced up version of the Singly and Doubly Linked List implementations in my own terms. In addition, as the name suggests, the basic internal is that the Linked List is being circular. Now time to clear out the 3rd element in the definition and explain
two distinct characteristics in the Circular Linked List;

  1. The head and the tail of the data structure don’t point to NULL, but head’s previous reference, points to tail and tail’s next reference points to the head,
  2. Circular List can be made using Singly or Doubly Linked List implementations.
Singly Circular Linked List

Doubly Circular Linked List

Operations

Operation description goes here

  • isEmpty: Checks whether the Linked List is empty,
  • insertFirst: Inserts the given Node to the head of Linked List,
  • insertAfter: Inserts the given Node after the existing Node in Linked List, 
  • insertLast: Inserts the given Node at the end of Linked List, 
  • deleteFirst: Deletes the Node in the head of Linked List,
  • deleteNode: Deletes the given Node in Linked List,
  • deleteLast: Deletes the given Node from the end of Linked List,
  • containsIterativeSearch: Iteratively searches Linked List,
  • containsRecursiveSearch: Recursively searches Linked List.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures To see how the code works, you can also check its Unit Test.

Queue

Reading Time: 2 minutes

Definition

Queue is a linear data structure that maintains FIFO setting; First In First Out. Queue comes in two possible internal implementations; Singly Linked List or Array. When think of FIFO, we can assume a group of people waiting queued up for buying a cinema ticket. The first person in the queue gets to buy the ticket and it follows the rest of the people in the queue.

Sample Queue Usage Areas

  • Hardware Scheduling; CPUs and Disks are properly scheduled in the concurrent environments,
  • Asynchronous communication makes a great use case while two processes wait for each other to respond in sequence

Implementation

In the internally Queue can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.

Complexity of Queue

Since the internals of implementations differ for each variationSingly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;


image courtesy of  bigocheatsheet.com

Operations on Queue


Queue has three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Queue implementation. However, these below operations are fundamental properties of the Queue data structure:

  • enqueue:  inserts the element to the head of the stack,
  • denqueue: removes the element from the head  and returns
    denqueued the value,
  • peek: returns the head data but doesn’t delete it, takes a peek at it.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.

Stack

Reading Time: 2 minutes

Definition

Stack is a very usable data structure that brings the LIFO setting into the game. Let’s elaborate LIFO; LIFO is the abbreviation of Last-In-First-Out. What does LIFO really mean for us? The intentions may vary and one of them is to have a pile of things stacked down to the bottom and take one from the top. Let’s apprehend the below illustration:

Yes, we understood it well. In the LIFO setting we insert towards bottom and and take from the top.

Sample Stack Usage Areas

  • In text editors “Undo” operations while we intend to revert an unwanted entry,
  • Browsers’ back buttons; make use of a similar way to be able to navigate to the earlier pages,
  • Recursive methods also utilize stack very well; starting from the first call till the last, all of the method executions are added on top of each other.

Implementation

In the internally Stack can implement Singly Linked List or Array. Eventually the Time Complexity of the operations will slightly differ. In this stackoverflow Article, there are more insights and argument about the implementations. In my own implementation I preferred to use the Singly Linked List implementation.

Complexity of Stack

Since the internals of implementations differ for each variation; Singly Linked List and Array, the operations can differ. The given table is suitable for Singly Linked List implementation;

image courtesy of  bigocheatsheet.com

Operations on Stack

Stack has three vital operations that we need to cover up. In some other languages and Stack implementations definitely have other additional operations like Java’s Stack implementation. However, these below operations are fundamental properties of the Stack data structure:

  • push: pushes the element on top of stack
  • pop: pops the element from the top and returns popped the value
  • peek: returns the head data but doesn’t delete it, takes a peek at it.

Code

The code can be also found in my Github Repository @ https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures to see how the code works, you can also check its Unit Test.

Binary Tree

Reading Time: 6 minutes

Definition

Binary tree is a non-linear data structure that is composed of two nodes at most. This is how the name “Binary” is formed. However, it is not necessary for the Child Nodes that they have to have two nodes, in fact they can have even zero, we will observe such types in the following chapters.

Furthermore, there is also a Binary Tree implementation called “Binary Search Tree(a.k.a ordered binary tree)” that preserves data in a sorted fashion. From this point on, we will be talking and focusing on Binary Search Tree. Let’s apprehend the characteristics of Binary Search Tree:

  • Given key is compared to the root key, the lower placed on the left and the greater placed on the right,
  • There are two ways of traversals; breadth first and depth first (will be detailed in a sub chapter) compared to one-dimensional arrays and linked lists,
  • Average cases of Positional Access, Search, Insertion and Deletion operations are far faster in tree that is denoted as O(log n) in the Big O time complexity.

Additionally, during my research, I have found a very useful resource that exposes a visualized Binary Search Tree and its operations; https://www.cs.usfca.edu/~galles/visualization/BST.html

Let’s look into the source code how we can create a Binary Tree.

Node.java

public class Node {
    Node leftNode;
    Node rightNode;
    int key;

    Node(int key) {
        this.key = key;
    }
}

BinaryTree.java

public class BinaryTree {

    private Node rootNode;
    private final static int DATA_NOT_AVAILABLE = -1;

//The rest of the code can be obtained on GitHub
}

Glossary and Properties

Before diving into Binary Search Tree, we will need to have a ubiquitous language to apprehend all the terms used in this data structure.

Binary Tree Glossary

Root: The only top most element that has no other nodes above it,

Node: Every member in the tree is known as Node including the root as well,

Parent Node: The node that has two children,

Child Node: A node that is associated with a parent node

Leaf: A leaf is a node that DOES NOT have any children,

Path/Edge: The lines that connect all available nodes,

Sub tree: It is a triangle shape in a tree. Essentially a parent with its two child nodes,

Height: The height of a tree is the number of the edges from the Root node to its deepest leaf.

Some Binary Tree Height Samples as follow:

Binary Tree Glossary Height is three

Binary Tree Glossary height is four

Time and Space Complexities of Binary Tree

Binary Tree Big O Notation Image courtesy: www.bigocheatsheet.com

Types of Binary Trees

Balanced Binary Tree

Balanced and Unbalanced Trees

A Balanced Tree is composed of a balance between the left and the right nodes, but at most one side differs only by one, otherwise it will be considered as an Unbalanced Tree. The operations in a balanced tree are performed in O(log n) notation where n is the node number.
In Addition, Balanced Tree Type has other implementations such as AVL, Red-Black, Weight and Height Balanced Trees etc. It is a good practice to apprehend the definition of the balanced tree.

Unbalanced Binary Tree

Unbalanced Tree

Ordered data sets make up the unbalanced tree. In this type, most of the nodes are located on one side of the tree. In Unbalanced Trees, we cannot favor of fast operations denoted as O(log n), whereas it is actually O(n).

Full Binary Tree

Full Binary Tree

Full Binary Tree is a tree type that consists of a rule that indicates that leaves can have zero or nodes have two children.

L + I + 1

L: Number of leaf nodes,

I: Number of internal nodes

Complete Binary Tree

Complete Binary Tree

Complete Tree is a type of a Binary Tree in which;

  1. Every level must be completely filled,
  2. All leaf elements must lean towards left direction,
  3. Exceptionally the last leaf might have a right child node

Furthermore, Complete Binary Tree is also a Heap

Perfect Binary Tree

Perfect Binary Tree consists of Full and Complete Binary Trees with two conditions of :

  • all nodes have two children,
  • all leaves are on the same level.

In addition, the height of tree is 2h – 1

Tree Traversal

Tree Traversal is the acronym that is known as Tree Search is a type of an action that leads to visiting every single node in the tree and performing selection, insertion, updating and deletion. While going/traversing through there are number of ways to do so namely; Breadth First and Depth First traversals.

Tree Traversal

Breadth First Traversal

Breadth First Tree Traversal

Breadth First Traversal traverses the tree in a level fashion. It internally utilizes a Queue Data Structure, to visit nodes in layers as you can see the illustration. The algorithm of Breadth First Traversal goes;

public void breadthFirstTraversal() {
        if (rootNode == null)
            return;
        System.out.printf("***Breadth First Traversal***\n");
        Queue<Node> queue = new ArrayDeque<>();
        queue.add(rootNode);
        while (!queue.isEmpty()) {
            rootNode = queue.remove();
            System.out.println(rootNode.key);
            if (rootNode.leftNode != null)
                queue.add(rootNode.leftNode);
            if (rootNode.rightNode != null)
                queue.add(rootNode.rightNode);
        }
}

Console Output:

***Breadth First Traversal***
60
55
67
50
57
61
77
45
53

Depth First Traversal

Deep First travel is slightly different and more complicated compared to the Breadth first traversal. Basically, Depth first traversal, the actual focus is not the levels and layers but the Depth itself. Depth first algorithms will visit each node.

In Order Traversal

In Order Traversal

In Order Traversal has the following sequence:

  1. Left Node,
  2. Root Node,
  3. Right Node

Having said that when the traversal begins from the deepest left node. As the second item goes to the root, it is not the top root but the parent root. Then it follows the right node. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void inOrderTraversal(Node node) {

        if (node != null) {

            inOrderTraversal(node.leftNode);

            System.out.println(node.key);

            inOrderTraversal(node.rightNode);

        }

    }

Console Output:

***In Order Traversal***
45
50
53
55
57
60
61
67
77

Pre Order Traversal

Pre Order Traversal

Pre Order Traversal has the following sequence:

  1. Root Node,
  2. Left Node,
  3. Right Node

Having said that when the traversal begins from the root node. As the second item goes to the next left root. Then here the algorithm starts to visit the left and accordingly the right node. As you see the above illustration, the algorithm starts in “60” the root node and ends in “77” the highest right node in the tree. Observe the code for traversal:

private void preOrderTraversal(Node node) {

        if (node != null) {

            System.out.println(node.key);

            preOrderTraversal(node.leftNode);

            preOrderTraversal(node.rightNode);

        }

    }

Console Output:

***Pre Order Traversal***
60
55
50
45
53
57
67
61
77

Post Order Traversal

Post Order Traversal

Post Order Traversal has the following sequence:

  1. Left Node,
  2. Right Node,
  3. Root Node

Having said that when the traversal begins from the deepest left node. As the second item goes to the next right node. Last of all it visits the root node of the children. As you see the above illustration, the algorithm starts in “45” the deepest left node and ends in “60” the root node. Observe the code for traversal:

private void postOrderTraversal(Node node) {

        if (node != null) {

            postOrderTraversal(node.leftNode);

            postOrderTraversal(node.rightNode);

            System.out.println(node.key);

        }

    }

Console Output:

***Post Order Traversal***
45
53
50
57
55
61
77
67
60

Code

The full source code of the Binary Tree and the test cases can be obtained from my public GitHub repository. There will be more utility methods and test cases covering the chapter.

https://github.com/tugrulaslan/BlogCodeSnippets/tree/master/DataStructures