Q3Design and Analysis of Algorithms
Question
2 marks
Define Heap.
Answer
A Heap is a complete binary tree satisfying the heap property: max-heap (parent ≥ children) or min-heap (parent ≤ children).
A Heap is a specialized tree-based data structure that satisfies the heap property. It is a complete binary tree (all levels filled except possibly the last, which is filled left to right). Stored efficiently in an array: for node at index i, left child is at 2i+1, right child at 2i+2, parent at (i-1)/2.
Max-Heap: Every parent node is greater than or equal to its children. Min-Heap: Every parent node is less than or equal to its children. Operations: Build Heap O(n), Insert O(log n), Extract-Max/Min O(log n). Used in Heap Sort, Priority Queues, Dijkstra's and Prim's algorithms.