Heap (data structure) facts for kids
In computer science, a heap is a type of tree (data structure) that satisfies the heap property. Heaps are useful when you need to remove the item with the highest (or lowest) value. A common implementation of a heap is the binary heap in which the tree is a complete binary tree.
Heap property
- In a max-heap, the value of each item is less than or equal to the value of its parent, with the maximum-value item at the root.
- In a min-heap, the value of each item is greater than or equal to the value of its parent, with the minimum-value item at the root.
Operations
- find: return a maximum item of a max-heap or a minimum item of a min-heap.
- insert: add a new item to the heap.
- extract: returns the maximum item from a max-heap (or minimum item from a min-heap) after removing it.
- delete: removes the root of a max-heap (or min-heap).
- size: return the number of items in the heap.
- is-empty: return true if the heap is empty, false otherwise.
Maintaining the heap property
- insert: insert the item at the bottom rightmost location; swap the item with its parent until the heap property is preserved.
- delete: remove the root; swap it with the item at the bottom rightmost location; swap the new root downwards with the smaller of its children until the heap property is preserved.
See also
In Spanish: Montículo (informática) para niños
All content from Kiddle encyclopedia articles (including the article images and facts) can be freely used under Attribution-ShareAlike license, unless stated otherwise. Cite this article:
Heap (data structure) Facts for Kids. Kiddle Encyclopedia.