The Gateway to Computer Science Excellence
+18 votes

Statement for Linked Answer Questions 76 & 77:

A $3$-ary max heap is like a binary max heap, but instead of $2$ children, nodes have $3$ children. A $3$-ary heap can be represented by an array as follows: The root is stored in the first location, $a[0]$, nodes in the next level, from left to right, is stored from $a[1]$ to $a[3]$. The nodes from the second level of the tree from left to right are stored from $a[4]$ location onward. An item $x$ can be inserted into a $3$-ary heap containing $n$ items by placing $x$ in the location $a[n]$ and pushing it up the tree to satisfy the heap property.

76. Which one of the following is a valid sequence of elements in an array representing $3$-ary max heap?

  1. $1, 3, 5, 6, 8, 9$
  2. $9, 6, 3, 1, 8, 5$
  3. $9, 3, 6, 8, 5, 1$
  4. $9, 5, 6, 8, 3, 1$
in DS by Active (3.3k points)
edited by | 1.5k views

2 Answers

+11 votes
Best answer
The method to solve is clearly given in the question itself. Just one thing to mention is the heap property. Max Heap = The parent is always greater or equal to the child. if not then swap the respective child with the parent to satisfy the property of the heap.
by Boss (19.9k points)
selected by
+7 votes

Heap has important property if it max heap then parent always greater than or equal to its two child... dont matter lest or right child in any oder..

and one important property if left child present then only right present ... i.e. it is not the case right child present but left child not present...

 if it min heap then parent always less than or equal to its two child..

Heap stored in array as

Parent then left child then right child.. then left child as root then its left chils then right child.....

if any place some thing mis then vacant thats place in array..

by Veteran (63k points)
edited by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,367 answers
105,266 users