Heap
lastmod 2020-09-13created 2015-11-111 edits
A heap is a data structure (tree-based structure) based on a complete binary tree, designed to speed up operations that find the maximum and minimum values, and it satisfies the following heap property.
If A is the parent node of B, an ordering holds between the key value of A and the key value of B. There are two kinds of heaps: a heap in which the parent node's key is always greater than the child nodes' keys is called a 'max heap', and a heap in which the parent node's key is always smaller than the child nodes' keys is called a 'min heap'.
The ordering of key values holds only between parent and child nodes; in particular, no ordering is defined between siblings.
The maximum number of child nodes per node depends on the kind of heap, but in most cases a binary heap, in which each node has at most 2 children, is used.
In a heap, the node with the highest (or lowest) priority is always at the root node, and using this, abstract data types such as a priority queue can be implemented.