Related Topics
Data Structure
What is a heap and what are its characteristics?
A heap is a special kind of binary tree-based data structure that satisfies the heap property.
The heap property can be either of two types:
Max-Heap property: In a max-heap, the value of each node is greater than or equal to the values of its children nodes. Thus, the maximum element is always stored at the root.
Min-Heap property: In a min-heap, the value of each node is less than or equal to the values of its children nodes. Thus, the minimum element is always stored at the root.
The two main characteristics of a heap are:
Shape Property: A heap is a complete binary tree, which means that all levels of the tree are completely filled except possibly the last level. The last level is filled from left to right.
Heap Property: A heap must satisfy the heap property, which means that for every node in the heap, the key of the parent node is either greater than or equal to (in the case of a max-heap) or less than or equal to (in the case of a min-heap) the keys of its children nodes.
The combination of these two properties allows efficient access to the maximum or minimum element in the heap, which can be useful in many algorithms and applications.
Explain the difference between a min heap and a max heap?
A heap is a specialized tree-based data structure in which the tree is a complete binary tree. A complete binary tree is a binary tree in which all levels are filled, except possibly the last one, which is filled from left to right. A heap can be of two types: a min heap and a max heap.
In a min heap, the value of each parent node is less than or equal to its children, so the root node has the minimum value of all the nodes in the heap. In other words, the key of each node is greater than or equal to the key of its parent node. This means that the smallest element in the heap is always at the root.
On the other hand, in a max heap, the value of each parent node is greater than or equal to its children, so the root node has the maximum value of all the nodes in the heap. In other words, the key of each node is less than or equal to the key of its parent node. This means that the largest element in the heap is always at the root.
The main difference between a min heap and a max heap is the order in which the nodes are arranged. In a min heap, the smallest value is at the root, while in a max heap, the largest value is at the root.
How to implement a min heap or a max heap in code?
Here’s an example implementation of a min heap in Python using a list:
class MinHeap:
def __init__(self):
self.heap = []
def parent(self, i):
return (i - 1) // 2
def left_child(self, i):
return 2 * i + 1
def right_child(self, i):
return 2 * i + 2
def swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def heapify_up(self, i):
while i > 0 and self.heap[i] < self.heap[self.parent(i)]:
self.swap(i, self.parent(i))
i = self.parent(i)
def heapify_down(self, i):
while (left := self.left_child(i)) < len(self.heap):
right = self.right_child(i)
min_child = left if right >= len(self.heap) or self.heap[left] < self.heap[right] else right
if self.heap[i] <= self.heap[min_child]:
break
self.swap(i, min_child)
i = min_child
def insert(self, val):
self.heap.append(val)
self.heapify_up(len(self.heap) - 1)
def extract_min(self):
if len(self.heap) == 0:
return None
min_val = self.heap[0]
self.swap(0, len(self.heap) - 1)
self.heap.pop()
self.heapify_down(0)
return min_val
This implementation uses a list to store the heap and provides methods to insert elements into the heap and extract the minimum value. The heapify_up and heapify_down methods are used to maintain the heap property. The insert method adds a new element to the end of the list and then performs heapify_up to ensure that the new element is in the correct position. The extract_min method removes the minimum element (which is always at the root of the heap) by swapping it with the last element in the list, removing the last element, and then performing heapify_down to restore the heap property.
To implement a max heap, you can simply reverse the comparison operators (< becomes > and vice versa) in the heapify_upandheapify_down` methods.
Explain the concept of a complete binary tree and how it relates to a heap?
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. This means that if the last level is not full, the nodes in that level are filled from left to right.
A heap is a special kind of complete binary tree in which every parent node is either greater than or equal to (in a max heap) or less than or equal to (in a min heap) its child nodes. In other words, the value at each node is greater than or equal to (in a max heap) or less than or equal to (in a min heap) the values at its child nodes.
The relationship between a complete binary tree and a heap is that a heap is always a complete binary tree, but not all complete binary trees are heaps. In a heap, the root node always has the highest (in a max heap) or lowest (in a min heap) value in the tree. This property allows for efficient insertion and removal of elements, as well as fast access to the minimum or maximum element in the heap.
How to insert a new element into a heap?
To insert a new element into a heap, you would follow these steps:
Add the new element to the bottom level of the heap, at the leftmost open position.
Compare the value of the new element with its parent. If the new element is smaller than its parent (in a min heap) or larger than its parent (in a max heap), swap the two elements.
Continue comparing and swapping the new element with its parent until the heap property is restored.
Here is an example implementation in Python for inserting a new element into a min heap:
def insert(heap, value):
heap.append(value)
index = len(heap) - 1
while index > 0:
parent_index = (index - 1) // 2
if heap[index] < heap[parent_index]:
heap[index], heap[parent_index] = heap[parent_index], heap[index]
index = parent_index
else:
break
The heap parameter is a list representing the heap, and the value parameter is the new element to be inserted. The append() method adds the new element to the end of the list. The index variable is initialized to the index of the new element, and the loop continues until the heap property is restored. The parent_index variable is calculated using integer division, and the comparison and swap are performed if necessary. The loop ends when the new element is in the correct position in the heap.
How to delete an element from a heap?
To delete an element from a heap, we first remove the root node and then restore the heap property.
Here are the steps to delete an element from a max heap:
Replace the root node with the last leaf node of the heap.
Remove the last leaf node of the heap.
If the new root violates the max heap property, swap it with its largest child until the max heap property is restored.
Here are the steps to delete an element from a min heap:
Replace the root node with the last leaf node of the heap.
Remove the last leaf node of the heap.
If the new root violates the min heap property, swap it with its smallest child until the min heap property is restored.
Implement a heap sort algorithm?
Here is an implementation of the heap sort algorithm in Python:
def heapify(arr, n, i):
# Find the largest element among root, left child and right child
largest = i # Initialize largest as root
l = 2 * i + 1 # left child = 2*i + 1
r = 2 * i + 2 # right child = 2*i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
# If root is not the largest element, swap with largest
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
# Heapify the affected sub-tree
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# Build a max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements one by one
for i in range(n - 1, 0, -1):
# Move current root to end
arr[i], arr[0] = arr[0], arr[i]
# Call max heapify on the reduced heap
heapify(arr, i, 0)
return arr
The heapify function is used to maintain the heap property, and the heap_sort function builds a max heap from the input array, and then repeatedly extracts the maximum element and places it at the end of the array until the entire array is sorted. The time complexity of heap sort is O(n log n), and it has the advantage of being an in-place sort, meaning it does not require extra space beyond the input array.
Questions on Chapter 9