1
$\begingroup$

I find this extremely wrong, that a lot of books, articles, video tutorials, online courses or trainers define Minimum/Maximum Heap data structure as a particular type of the Binary Heap data structure.. however! according to the definition of what is Heap Data Structure, that's wrong! Heap can be perfectly fine either Binary or non-Binary.

I have also read this in some Google Engineer's blog, that my thoughts are correct on this.

Any take? maybe I'm wrong? nothing, at all, restricts the Minimum/Maximum Heap that they must be necessary Binary Heap variations. Node can have 3 children, and it would still fit the Minimum/Maximum Heap definition.

Question is: how do you think? am I wrong or not? what's your take on this?

$\endgroup$
10
  • 3
    $\begingroup$ What is a heap for you? This is the root of the question. I'm not sure there is a single agreed upon formal definition of heap. $\endgroup$ Commented Apr 10, 2020 at 15:43
  • $\begingroup$ Tree-based data structure, which satisfies Heap order invariant (either max, min, or etc.). Yes, that's what I'm asking.. that nothing says, that Heap is a necessarily Binary-Tree based data structure. $\endgroup$ Commented Apr 10, 2020 at 16:19
  • 1
    $\begingroup$ So your definition doesn't specify the number of children. Therefore, under your definition, we tautologically have that a heap need not be a binary tree. $\endgroup$ Commented Apr 10, 2020 at 16:20
  • 4
    $\begingroup$ You're assuming that there is a single, accepted upon definition. I'm not sure your assumption is correct. $\endgroup$ Commented Apr 10, 2020 at 16:25
  • 4
    $\begingroup$ There isn't even an agreed upon definition of standard models such as DFA and Turing machine. $\endgroup$ Commented Apr 10, 2020 at 16:29

2 Answers 2

1
$\begingroup$

A heap can be binary or k-ary, so it's fine to think like you do, in my opinion. Binary heaps are more common to think about. The time complexities for the different heap operations change for the better or worse as we vary k.

$\endgroup$
0
$\begingroup$

Instead of "heap", think "priority queue". A priority queue is a data structure where elements can be inserted in any order, but are removed in key order.

We will suppose that the priority queue uses a comparison operator (say, less-than) to determine key order. (This need not be the case; if the keys are integers, for example, you could use a radix operator.) We will further suppose that it is a min-queue, where elements are removed in ascending order (that is, the first element is the minimum).

Then simply reversing the sense of the comparison operator gives a max-queue.

Heaps (in their many forms) are one way of implementing priority queues, just like how balanced binary search trees (in their many forms) are one way of implementing key-value dictionaries. But they are not the only way.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.