Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms (Data structures (Heap # (Procedures (MAX-HEAPIFY
O(lg n)…
Algorithms
Data structures
-
-
-
Procedures
-
-
-
MAX-HEAP-INSERT;
HEAP-EXTRACT-MAX;
HEAP-INCREASE-KEY;
HEAP-MAXIMUM;
O(lg n) running time
allows to implement a priority queue
-
-
-
-
Binary tree consists of a finite set of nodes that is either empty or consists of one specially designated node called root of the binary tree, and the elements of two disjoint binary trees called left and right subtrees
A complete binary tree of depth d is a tree with all the leaves at the level d
- total number of nodes is (2^d+1) - 1
- tree contains 2^d leaves
A binary tree is almost complete if:
- Each leaf in the tree is either at level d or level d -1
- For any node n in the tree with a right descendant at level d, all the left descendants of n that are leaves are also at level d
-
-
-