CODEWITHSUNDEEP
algorithmdata-structureslanguage-agnosticheap
user1410825
user1410825

Reputation: 11

Create a heap by inserting the following elements in the order

The question:

Create a heap by inserting the following elements in the order that they are given. Show the heap after each insertion and trickle. (The heap should be implemented to keep the highest key value at the top.)

5 4 6 7 9 8 1 2 3

Once you have finished creating the heap, remove each element from it. Show the heap after each removal and trickle. Indicate which element has been removed in each step.

I know how to insert an element into the heap, but how to create it ? And I am really not sure how to remove the element from the heap.

Upvotes: 0

Views: 1828

Answers (1)

timos
timos

Reputation: 2707

I will assume a binary heap for my answer, there are many different heaps, but since this sounds like homework and is a fairly basic question I wil cover the most basic heap there is:

Well, first the heap is empty.

Then you insert 5, so the heap is now:

5

Then you insert 4 at the bottom. 4 is smaller than 5, so we do not change its position with it's parent. The heap is now:

   5
  /
 4

Then we insert 6 at the bottom, below the 5 (always insert at the bottom from left to right). We compare the value of the newly inserted node (6) with it's parent (5) and realize we have to swap them, to not violate the heap property:

   6
  / \
 4   5

Now we insert 7 at the next available spot (below the 4), and swap it with it's parent because 7 > 4. Then we swap (or trickle) again, as 7 > 6 and get:

    7
   / \
  6   5
 /
4

and so on...

Upvotes: 1

Related Questions