CODEWITHSUNDEEP
data-structures
NB25
NB25

Reputation: 21

Questions on Binary Heap Data structure

I've been reading on different websites and books and I have some questions I need some clearing up on with heaps.

1: Is the priority of a parent node is always higher than the priorities of either of its children?

2: Is the priority of a left sibling is always lower than the priority of its right sibling?

3: Is Every level full except possibly the top level, which is right-loaded?

4: Is Every level full except possibly the bottom level, which is left-loaded.

Upvotes: 1

Views: 663

Answers (2)

user7571182
user7571182

Reputation:

Before understanding anything about heaps, you should know the definitions of complete binary tree(CBT) and almost complete binary tree(ACBT).

CBT AND ACBT

Complete Binary Tree: A complete binary tree is a tree in which every node other than leaves has two children.

Almost Complete Binary tree: In the given binary tree at every node:

  1. After filling left-child then only fill the right-child.
  2. After filling the current level then only fill the next level.

Now, let us look at the definition of binary heap:

A binary heap is a complete binary tree or almost complete binary tree (All levels are completely filled except possibly the last level has all keys as left as possible i.e. left-loaded). This property is suitable to store heap in arrays.

Types of binary heap:

Max heap: In the given ACBT or CBT; parent root is maximum or equal comparing its children.

Min heap: In the given ACBT or CBT; parent node is minimum or equal comparing its children.

This explanation will clarify your all the questions, but let me summarize it for you.

  1. Priority is not a thing here. Here, whatever order(based on Max or Min heap) you are following, you have to follow for every node. The only point you need to keep in mind is in case of Max Heap parent node is maximum or equal than its children and vice-versa in min heap. You don't care about left or right child. This is taken care in Binary Search Tree(BST).

  2. All levels are full except possibly the last level has all the keys(by keys I mean children) as left as possible.

  3. In binary heap, if the heap is a complete binary tree with N nodes, then it has has smallest possible height which is log2N.

There is an amazing link which you can refer to get the better insights on heaps.

Upvotes: 1

Jim Mischel
Jim Mischel

Reputation: 134125

From https://en.wikipedia.org/wiki/Binary_heap:

A binary heap is defined as a binary tree with two additional constraints:[3]

  • Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
  • Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

As for your questions:

1: Is the priority of a parent node is always higher than the priorities of either of its children?

In a max-heap, the priority of the parent node is always greater than or equal to the priority of its children.

2: Is the priority of a left sibling is always lower than the priority of its right sibling?

Absolutely not! Both of the following are valid max-heaps:

  3           3
 / \         / \
2   1       1   2

Trying to maintain the ordering of left and right children, while maintaining the Shape property is a fool's errand. It can be done, but at great cost to efficiency.

For questions 3 and 4, see the discussion of the Shape property above. In particular.

3: Is Every level full except possibly the top level, which is right-loaded?

No.

4: Is Every level full except possibly the bottom level, which is left-loaded.

Yes. That's what the Shape property says.

Upvotes: 1

Related Questions