Question

How ot construct the Min heap

How to construct the Min heap of the following:

82, 90, 10, 12, 15, 77, 55, 23


Submit an answer


This textbox defaults to using Markdown to format your answer.

You can type !ref in this text area to quickly search our full set of tutorials, documentation & marketplace offerings and insert the link!

Sign In or Sign Up to Answer

These answers are provided by our Community. If you find them useful, show some love by clicking the heart. If you run into issues leave a comment, or add your own answer to help others.

Bobby Iliev
Site Moderator
Site Moderator badge
October 27, 2024

Hey!

What I would recommend here is to start by checking out this helpful tutorial: Min Heap Binary Tree Tutorial.

In general, a min heap is structured so that each parent node is smaller than its child nodes, with the smallest element at the root. For example, as you insert each number, swap elements as needed to keep this order.

For your exact question, this would look like:

  1. Insert 82, 90, 10, 12, 15, 77, 55, 23 one by one.
  2. After each insertion, adjust (or “heapify”) to ensure each parent node is smaller than its children.

Hope this helps!

- Bobby

KFSys
Site Moderator
Site Moderator badge
October 28, 2024

Heya,

To construct a Min-Heap from the list of values (82, 90, 10, 12, 15, 77, 55, 23), we’ll insert each element one-by-one, ensuring that the heap property is maintained at each step. The Min-Heap property requires that each parent node is less than or equal to its child nodes.

Let’s go through the insertion and rebalancing process for each element:

Step-by-Step Insertion and Heapify

  1. Start with an empty Min-Heap.

  2. Insert 82:

    • Heap: [82]
  3. Insert 90:

    • Heap: [82, 90]
    • 90 is greater than 82, so the heap property holds.
  4. Insert 10:

    • Heap: [82, 90, 10]
    • 10 is less than 82, so swap them to maintain the Min-Heap property.
    • Heap after swap: [10, 90, 82]
  5. Insert 12:

    • Heap: [10, 90, 82, 12]
    • 12 is greater than 10, so no swaps are needed.
  6. Insert 15:

    • Heap: [10, 90, 82, 12, 15]
    • 15 is greater than 10, so no swaps are needed.
  7. Insert 77:

    • Heap: [10, 90, 82, 12, 15, 77]
    • 77 is greater than 10, so no swaps are needed.
  8. Insert 55:

    • Heap: [10, 90, 82, 12, 15, 77, 55]
    • 55 is greater than 10, so no swaps are needed.
  9. Insert 23:

    • Heap: [10, 90, 82, 12, 15, 77, 55, 23]
    • 23 is greater than 10, so no swaps are needed.

Final Min-Heap

After all insertions, the heap structure, arranged to meet the Min-Heap property, is:

        10
       /  \
     12    77
    /  \   / \
   23  15 90  55
            \
            82

So, the array representation of this Min-Heap is:

[10, 12, 77, 23, 15, 90, 55, 82]

Become a contributor for community

Get paid to write technical tutorials and select a tech-focused charity to receive a matching donation.

DigitalOcean Documentation

Full documentation for every DigitalOcean product.

Resources for startups and SMBs

The Wave has everything you need to know about building a business, from raising funding to marketing your product.

Get our newsletter

Stay up to date by signing up for DigitalOcean’s Infrastructure as a Newsletter.

New accounts only. By submitting your email you agree to our Privacy Policy

The developer cloud

Scale up as you grow — whether you're running one virtual machine or ten thousand.

Get started for free

Sign up and get $200 in credit for your first 60 days with DigitalOcean.*

*This promotional offer applies to new accounts only.