3

The clear difference is that a red-black tree can support O(logn) removal, compared to heap's O(n) removal.

However, it looks like all operations for a red-black tree are faster/equal tothose of a heap. So my question is, why do we ever use a heap over red-black tree? It seems to me a red-black tree can do anything a heap can do, but faster/equal.

Thanks.

Wonjoo Lee
  • 99
  • 3
  • 8
  • This Question is not related to programming basicly, ask it in https://cs.stackexchange.com/ which is primarily designed to issues like yours. – Adnan Ahmad Khan Mar 21 '19 at 06:15
  • 1
    Why O(n)? When you remove the root (it's probably why the data structure is used in the first place), it's O(log n). As for the benefits, links between nodes aren't needed, so, you may heapify and sort an array in place. – Alexey Frunze Mar 21 '19 at 07:39
  • Thanks for asking this question, I found it here on stackoverflow and then saw the answer on cs questions. If you didn't ask it here, I would have never found it. – Noitidart Mar 30 '19 at 21:46

1 Answers1

0

A principal use case for a minheap is a priority queue where the main operations as push(newval), pop_smallest(), inspect_smallest().

In this situation a heap wins because the inspect_smallest() search step is O(1). The smallest value is always at position zero.

Also, while both Red Black Trees and Minheaps have O(log n) insertion and removal times, the constant factor is smaller for minheaps.

Also, heaps can be represented much more compactly than for a red-black tree. There is no need for a "coloring" bit and the tree itself is easily represented as an array, so there is no need to store pointers.

In short, if an application doesn't need general search and can instead focus on the lowest value, then a heap provides a simpler and cheaper alternative.

Raymond Hettinger
  • 216,523
  • 63
  • 388
  • 485