In computer science, a heap is a specialized tree-based data structure that satisfies the heap property: if B is a child node of A, then key(A) ≥ key(B). This implies that an element with the greatest key is always in the root node, and so such a heap is sometimes called a max-heap. (Alternatively, if the comparison is reversed, the smallest element is always in the root node, which results in a min-heap.) There is no restriction as to how many children each node has in a heap. The heap is one maximally-efficient implementation of an abstract data type called a priority queue. Heaps are crucial in several efficient graph algorithms such as Dijkstra's algorithm.
Heaps are usually implemented in an array, and do not require pointers between elements.
The operations commonly performed with a heap are:
- find-max or find-min: find the maximum item of a max-heap or a minimum item of a min-heap, respectively
- delete-max or delete-min: removing the root node of a max- or min-heap, respectively
- increase-key or decrease-key: updating a key within a max- or min-heap, respectively
- insert: adding a new key to the heap
- merge: joining two heaps to form a valid new heap containing all the elements of both.
Heaps are used in the sorting algorithm heapsort.
Master theorem
http://en.wikipedia.org/wiki/Master_theorem
No comments:
Post a Comment