Data Structures — Stack, Queue and Heap
Data structures rules the world of programming!
In this blog post, we’ll discuss three simple data structures stack, queue and heap & its implementation and also checkout its application and time complexity.
Stack
Stack is a simple data structure and it stores elements like pile of plates. Operation in stack is done on top of stack meaning, we can perform insertion and deletion on top pointer of stack.
Consider a pile of 10 numbered plates with 1 at the bottom and 10 at the top, to remove plate 5, we need to remove 10, 9, 8, 7, 6 then 5 in that order, to perform deletion. This procedure of deletion or accessing an element is called Last In First Out (LIFO). The things that comes last, will be removed first.
Basic operations in Stack
- Push — Adding element at the top of the stack
- Pop — Removing the top element from stack
- isEmpty — Check if stack is empty or not
- peek — Finding the top element from stack
- isFull — Check if stack is full or not
Stack Implementation
class stack:
def __init__(self):
self.stack = []
def push(self, element):
return self.stack.append(element)
def pop(self):
return self.stack.pop()
def isEmpty(self):
return len(self.stack) == 0
def peek(self):
if len(self.stack) != 0:
return self.stack[-1]
else:
return "Stack is Empty"
"""
create_stack = stack()
create_stack.push(5)
create_stack.push(2)
create_stack.push(3)
create_stack.push(4)
print(create_stack.stack)
`[5, 2, 3, 4]`
create_stack.pop()
`4`
create_stack.peek()
`3`
create_stack.pop()
create_stack.pop()
create_stack.pop()
create_stack.isEmpty()
`True`
create_stack.peek()
'Stack is Empty'
"""Time Complexity: For the array-based implementation of a stack, the push and pop operations take constant time, i.e. O(1).
Applications
- Reverse a string
- In browsers, the back button to keep track of all urls visited earlier.
Queue
Queue data structure follows the same operation as queue in real life. Like a queue while buying a ticket in a park, the person who buys the first ticket gets into the park first. It follows FIFO (First In First Out). Inserting into queue is called as enqueue and deletion of an element is called dequeue.
Basic operation in Queue
- Enqueue — Appending elements at the end of the queue
- Dequeue — Removing element from the front of the queue
- IsEmpty — Check if the queue is empty
- IsFull — Check if the queue is full
- Peek — Get the value of the front of the queue without removing it
Queue Implementation
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, element):
return self.queue.append(element)
def dequeue(self):
return self.queue.pop(0)
def isEmpty(self):
return len(self.queue) == 0
def peek(self):
if len(self.queue) != 0:
return self.queue[0]
else:
return "Queue is Empty"
'''
create_queue = Queue()
create_queue.queue
`[]`
create_queue.enqueue(1)
create_queue.enqueue(2)
create_queue.enqueue(3)
create_queue.queue
`[1, 2, 3]`
create_queue.dequeue()
`[1]`
create_queue.queue
`[2, 3]`
create_queue.peek()
`[2]`
create_queue.dequeue()
create_queue.dequeue()
create_queue.isEmpty()
`True`
create_queue.peek()
'Queue is Empty'
'''The time complexity of enqueue and dequeue operations in a queue using an array is O(1).
Other Types of Queue
- Circular Queue — In a circular queue, the last element points to the first element making a circular link.
- Priority Queue — Its a special type of queue in which each element is associated with a priority and is served according to its priority. If elements with the same priority occur, they are served according to their order in the queue.
Applications
- Disk Scheduling, CPU scheduling
- Call Center phone systems use Queues to hold people calling them in order.
Heap
Heap data structure is a complete binary tree that satisfies the heap property. A complete binary tree is a special binary tree in which
- every level, except possibly the last, is filled
- all the nodes are as far left as possible
- Max-Heap — key of each node is always greater than its child node/s and the key of the root node is the largest among all other nodes.
- Min-Heap — key of each node is always smaller than the child node/s and the key of the root node is the smallest among all other nodes.
There are various operations in heap like heapify, inserting in heap and deletion etc.
Heapify
It is process of creating a heap data structure from a binary tree. It is used to create Max-Heap and Min-Heap.
How to convert a binary tree into a heap data structure (max heap or min heap)
- Consider we have an array of 6 elements.
- We convert that array into a complete binary tree.
- A binary tree is filled from root node then to left and then to right and repeats (left and then right), at the bottom we have leaf node.
- Start from the first index of non-leaf node whose index is given by n/2–1. Since 6 elements, 6/2 -1 i.e. 2. Node at position 2 is selected.
- Set current element i as largest
- The index of left child is given by 2i + 1 and the right child is given by 2i + 2. If leftChild is greater than currentElement (i.e. element at ith index), set leftChildIndex as largest. If rightChild is greater than element in largest, set rightChildIndex as largest.
- Swap
largestwithcurrentElement
Insertion in Heap
To add a new element into existing heap, considering we have a max heap.
- If a node is present in existing heap with an empty child space, then we can add this new element as a child of that node, else we can create new node.
- Once we place the new node, we can heapify as we did above to keep intact the properties of max heap.
Deletion in Heap
To delete an element in heap, considering we have a min heap.
- Select the element to be deleted
- Swap the selected element with the last element of the heap.
- Remove the last element
- Heapify the tree.
Peek
To find max or min of an element in max or min heap, find the root node of the binary tree.
Min-Heap Implementation
# MIN HEAP
def heapify(array, n , i):
smallest_index = i
left_child_index = 2 * i + 1
right_child_index = 2 * i + 2
if left_child_index <= n and array[i] > array[left_child_index]:
smallest_index = left_child_index
if right_child_index <= n and array[smallest_index] > array[right_child_index]:
smallest_index = right_child_index
if smallest_index != i:
array[i],array[smallest_index] = array[smallest_index],array[i]
heapify(array, n, smallest_index)
print(array)
def insert(array, element):
size = len(array)
if size == 0:
array.append(element)
else:
array.append(element)
for i in range((size//2)-1, -1, -1):
heapify(array, size, i)
def deletion(array, element):
size = len(array)
i = 0
for i in range(0, size):
if element == array[i]:
break
array[i], array[size-1] = array[size-1], array[i]
array.remove(element)
for i in range((len(array)//2)-1, -1, -1):
heapify(array, len(array)-1, i)
array = []
insert(array, 7)
insert(array, 8)
insert(array, 3)
insert(array, 1)
insert(array, 9)
insert(array, 2)
insert(array, 5)
print ("Min-Heap array: " + str(array))
deletion(array, 9)
print ("Min-Heap array: " + str(array))
'''
[3, 8, 7]
[3, 8, 7]
[3, 8, 7, 1]
[3, 1, 7, 8, 9]
[3, 1, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9]
[1, 3, 7, 8, 9, 2]
[1, 3, 7, 8, 9, 2]
[1, 3, 2, 8, 9, 7, 5]
[1, 3, 2, 8, 9, 7, 5]
[1, 3, 2, 8, 9, 7, 5]
[1, 3, 2, 8, 9, 7, 5]
Min-Heap array: [1, 3, 2, 8, 9, 7, 5]
[1, 3, 2, 8, 5, 7]
[1, 3, 2, 8, 5, 7]
[1, 3, 2, 8, 5, 7]
Min-Heap array: [1, 3, 2, 8, 5, 7]
'''Applications
- Heap is used while implementing a priority queue.
- Dijkstra’s Algorithm
- Heap Sort
Thanks for reading. If you liked reading my articles, checkout Math + Computing = AI for more articles.
