Why are heaps in c++ implemented as algorithms instead of containers?

Question

I was wondering why the heap concept is implemented as algorithms (make_heap, pop_heap, push_heap, sort_heap) instead of a container. I am especially interested is some one's solution can also explain why set and map are containers instead of similar collections of algorithms (make_set add_set rm_set etc).

Answer 1

Well, heaps aren't really a generic container in the same sense as a set or a map. Usually, you use a heap to implement some other abstract data type. (The most obvious being a priority queue.) I suspect this is the reason for the different treatment.

Answer 2

One obvious reason is that you can arrange elements as a heap inside another container.
So you can call make_heap() on a vector or a deque or even a C array.

Answer 3

A heap is a specific data structure. The standard containers have complexity requirements but don't specify how they are to be implemented. It's a fine but important distinction. You can make_heap on several different containers, including one you wrote yourself. But a set or map mean more than just a way of arranging the data.

Said another way, a standard container is more than just its underlying data structure.

Answer 4

Heaps* are almost always implemented using an array as the underlying data structure. As such it can be considered a set of algorithms that operate on the array data structure. This is the path that the STL took when implementing the heap - it will work on any data structure that has random access iterators (a standard array, vector, deque, etc).

You'll also notice that the STL priority_queue requires a container (which by default is a vector). This is essentially your heap container - it implements a heap on your underlying data structure and provides a wrapper container for all of the typical heap operations.

*Binary heaps in particular. Other forms of heaps (Binomial, Fibonacci, etc) are not.

Answer 5

STL does provide a heap in the form of a std::priority_queue. The make_heap, etc., functions are there because they have uses outside the realm of the data structure itself (e.g. sorting), and to allow heaps to be built on top of custom structures (like stack arrays for a "keep the top 10" container).

By analogy, you can use a std::set to store a sorted list, or you can use std::sort on a vector with std::adjacent_find; std::sort is the more general-purpose and makes few assumptions about the underlying data structure.

(As a note, the std::priority_queue implementation does not actually provide for its own storage; by default it creates a std::vector as its backing store.)