Heap (data structure) facts for kids

Example of a binary max-heap containing items between 1 and 100.

In computer science, a heap is a special type of tree (data structure). Think of it like a family tree, but for numbers or other pieces of information. Heaps are super useful when you need to quickly find and remove the biggest (or smallest) item from a list. A common kind of heap is called a binary heap, which is a complete binary tree.

What is a Heap?

A heap follows a special rule called the heap property. This rule makes sure that the biggest (or smallest) item is always easy to find. There are two main types of heaps:

• Max-heap: In a max-heap, the biggest item is always at the very top (called the root). As you go down the tree, each item is smaller than or equal to its parent. So, a parent is always bigger than its children.
• Min-heap: In a min-heap, the smallest item is at the very top (the root). As you go down, each item is larger than or equal to its parent. Here, a parent is always smaller than its children.

How Heaps Work: Basic Actions

Heaps can do several helpful things with the information they store:

• Find: You can quickly find the biggest item in a max-heap or the smallest item in a min-heap. It's always at the top!
• Insert: You can add a new item to the heap. The heap will then rearrange itself to keep the heap property true.
• Extract: This action finds and removes the biggest item (from a max-heap) or the smallest item (from a min-heap). After it's removed, the heap rearranges itself again.
• Delete: You can remove the top item (the root) from the heap.
• Size: You can ask the heap how many items it currently holds.
• Is-empty: This tells you if the heap has any items in it at all.

Keeping the Heap Organized

When you add or remove items, the heap needs to stay organized so it still follows the heap property. This involves a few clever steps:

• Adding an item: When you add a new item, it first goes to the very end of the heap. Then, it "bubbles up" by swapping places with its parent if it's bigger (in a max-heap) or smaller (in a min-heap). This continues until it finds its correct spot.
• Removing an item: When you remove the top item, the last item in the heap takes its place. Then, this new top item "sinks down" by swapping with its largest (in a max-heap) or smallest (in a min-heap) child. This continues until it settles into the right spot.

See also

In Spanish: Montículo (informática) para niños