Why heap is better than binary tree to represent a

问题:

In a (max) heap it is easy to find the biggest item in O(1) time, but to actually remove it you need complexity of O(log(n)).

So if the insertion and deletion from a heap is both O(log(n)), what are the advantages of a heap over binary tree for representing a priority queue?

回答1:

1. Heaps use less memory. They can be implemented as arrays and thus there is no overhead for storing pointers. (A binary tree CAN be implemented as an array, but there is likely to be many empty "gaps" which could waste even more space than implementing them as nodes with pointers).

2. Heaps are guaranteed to have height of log(n), because they do not need to guarantee that elements can be retrieved in sorted order though an in-order traversal, only that a node's value dominates its children's values. This allows them to have their "packed" structure as an array. A binary tree (unless it is a balanced binary tree) will usually end up with with branches that have a height larger than log(n), so even though operations have the same big O complexity, in reality the heap will be slightly faster.

3. Since the heap can be implemented as an array you get a huge advantage of accessing contiguous memory that is likely still in the cache rather than accessing nodes pointed to by pointers who's memory is scattered all over the place.

4. Heaps are simpler to implement than binary trees (especially balanced binary trees)

A disadvantage is that with heaps you are not able to do a binary search, but for a priority queue you do not need this ability.