DS & Al - MCS103 - Module 3- Heaps and Balanced Search Trees

lOMoARcPSD|44613495




DS & Al- MCS103 - Module 3Notes


Data Structure and Algorithms for Problem solving (Visvesvaraya Technological
University)




Scan to open on Studocu




Studocu is not sponsored or endorsed by any college or university
Downloaded by Samuel Wachira ndiang'ui ()

, lOMoARcPSD|44613495




Data Structures & Algorithms for Problem Solving – MCS103 2024-25



Module 3
Heaps




Heap
A Heap is a complete binary tree that follows the heap-order property,
meaning:
 Max-Heap: The parent node is always greater than or equal to its
children.
 Min-Heap: The parent node is always smaller than or equal to its
children.
Properties of Heap:
1. Complete Binary Tree: All levels are completely filled except possibly
the last.
2. Heap-Order Property: The value of each parent node is either greater
(Max-Heap) or smaller (Min-Heap) than its children.
Applications: Used in priority queues, Dijkstra’s algorithm, and heapsort.


Balanced Search Trees as Heaps
In data structures, both Balanced Search Trees and Heaps are used for efficient
data retrieval, but they serve different purposes. However, a connection can be
established between them in terms of heap-order property and balanced height.
1. Balanced Search Trees
A Balanced Search Tree is a binary search tree (BST) that maintains a height
close to O (log n), ensuring efficient operations like insertion, deletion, and
searching. Examples include:
 AVL Trees (maintaining balance using height difference)
 Red-Black Trees (balancing using colour properties)
 B-Trees (used in databases, keeping nodes balanced)

Page 1 of 70


Downloaded by Samuel Wachira ndiang'ui ()

, lOMoARcPSD|44613495




Data Structures & Algorithms for Problem Solving – MCS103 2024-25



2. Heaps
A Heap is a specialized binary tree that follows the heap-order property:
 Max-Heap: The parent node is always greater than or equal to its
children.
 Min-Heap: The parent node is always smaller than or equal to its
children.
It supports efficient priority queue operations, with O (1) access to the root and
O (log n) insertions/deletions.
3. Balanced Search Trees vs. Heaps
Feature Balanced Search Tree Heap
Structure Binary Search Tree with Complete Binary Tree
balance constraints
Order Property In-order traversal gives No strict order, only
sorted elements heap property
Search Complexity O (log n) O (n) in the worst case
Insert/Delete O (log n) O (log n)
Complexity
Application Database indexing, Priority Queues,
efficient searching Scheduling

4. Balanced Search Trees as Heaps
Although Balanced Search Trees are mainly used for ordered retrieval, they can
simulate a Heap-like structure by:
1. Using the Root Node as a Min/Max Element: In a balanced BST, the
leftmost node contains the smallest element, similar to a Min-Heap. The
rightmost node contains the largest element, similar to a Max-Heap.
2. Heapifying a BST: If we maintain a complete binary tree property along
with a heap-order property, a BST can behave like a Heap.
3. Priority Queue Implementation: A balanced search tree like a Treap (Tree
+ Heap) combines the properties of a BST and a Heap, where the
structure follows a BST, and the values follow the heap property.
5. Balanced Search Trees and Heaps are closely related in terms of logarithmic
time complexity for insertions and deletions. However, Heaps prioritize
efficient root access, while Balanced Search Trees focus on ordered traversal.


Page 2 of 70


Downloaded by Samuel Wachira ndiang'ui ()

, lOMoARcPSD|44613495




Data Structures & Algorithms for Problem Solving – MCS103 2024-25



typedef struct { key_t key;
object_t *object;
}heap_el_t;
typedef struct { heap_el_t current_min;
tree_node_t *tree;
}heap_t;




heap_t *create_heap(void)
{
heap_t *hp;
hp = (heap_t *) malloc( sizeof(heap_t) );
hp->tree = create_tree();
return( hp );
}
int heap_empty(heap_t *hp)
{
return( hp->tree->left == NULL );
}
heap_el_t find_min(heap_t *hp)
{
return( hp->current_min );
}
void insert_heap( key_t new_key, object_t *new_obj, heap_t *hp)
{
If (hp->tree->left == NULL || new_key < hp->current_min.key )
{


Page 3 of 70


Downloaded by Samuel Wachira ndiang'ui ()