Which statement about a heap data structure is true?

• A. A heap is a nearly complete binary tree used to implement priority queues and for heap sort.
• B. A heap is a binary search tree optimized for quick min extraction.
• C. A heap is a graph that must be acyclic.
• D. A heap stores keys in strictly sorted order at all times.

Answer: (A)

A heap is a nearly complete binary tree, meaning all levels are filled except possibly the last, which is filled from left to right. This shape keeps the height small, so insertions and deletions happen in logarithmic time. The heap property—parents are always greater than (or less than) their children depending on whether it’s a max-heap or a min-heap—ensures the root holds the highest or lowest priority, which is why priority queues work so efficiently with heaps and why heapsort can build a sorted sequence by repeatedly removing the root and re-heapifying. This combination of shape and ordering makes heaps ideal for quickly accessing the top element and for sorting.

A binary search tree, on the other hand, enforces a strict in-order order across the entire tree, which isn’t what a heap guarantees. A heap is not a graph and doesn’t require acyclic properties in the sense graphs do; it’s a tree with a particular shape and partial ordering. Also, keys in a heap aren’t stored in strictly sorted order across the structure; only the root is guaranteed to be the extreme element, with the rest arranged to maintain the heap property.