What is a heap data structure and what are its primary operations?

What is a heap data structure and what are its primary operations?

• A. A heap is a stack; supports push and pop in O(1).
• B. A heap is a graph; supports shortest path and cycle detection.
• C. A heap is a linked list; supports append and remove in O(1).
• D. A heap is a complete binary tree that supports insert and extract-min/max in O(log n) time.

Answer: (D)

A heap is a tree-based data structure that maintains a partial order so the root is the smallest (min-heap) or largest (max-heap) element, and it is stored as a complete binary tree. Because the tree is complete, its height is logarithmic in the number of elements, which is what gives the usual insertion and removal times of O(log n). Insert adds the new element at the next available leaf and then bubbles up, swapping with its parent until the heap property holds; this keeps the root as the min or max. Extract-min or extract-max removes the root, moves the last element to the root, and then bubbles down by swapping with the appropriate child until the heap property is restored. Both operations take time proportional to the height, hence O(log n). Heaps are commonly stored in arrays, with simple index relations to navigate parent and children, which aligns with the complete-tree structure. This description matches a complete binary tree that supports insert and extract-min/max in O(log n) time.

A heap is a tree-based data structure that maintains a partial order so the root is the smallest (min-heap) or largest (max-heap) element, and it is stored as a complete binary tree. Because the tree is complete, its height is logarithmic in the number of elements, which is what gives the usual insertion and removal times of O(log n).

Insert adds the new element at the next available leaf and then bubbles up, swapping with its parent until the heap property holds; this keeps the root as the min or max. Extract-min or extract-max removes the root, moves the last element to the root, and then bubbles down by swapping with the appropriate child until the heap property is restored. Both operations take time proportional to the height, hence O(log n).

Heaps are commonly stored in arrays, with simple index relations to navigate parent and children, which aligns with the complete-tree structure. This description matches a complete binary tree that supports insert and extract-min/max in O(log n) time.