Heap

Dictionary

TREE

 - A connected undirected graph with no cycles.

BINARY TREE

 - A tree that is either empty or consists of a root node and two disjoint binary trees called the left subtree and the right subtree, respectively.

COMPLETE BINARY TREE

 - Binary tree obtained from a full binary tree by right-to-left elimination of nodes on the last level.

FULL BINARY TREE

 - Binary tree that has 2^k-1 vertices arranged on the levels 0,1, ..., k-1, so that on each level i are found 2^i vertices.

Introductory Notions

  1. Trees
  2. Binary trees
  3. Heaps

Min-Heap generator

Heap

  1. Creation
  2. Insert node
  3. Combination
  4. Extract node

Priority queue

Applications

Dictionary

STRICT BINARY TREE

 - Binary tree where any vertex has degree zero (is terminal) or degree two (has exactly two children).

ROOTED TREE

 - A finite set of nodes that is either empty or:
-- There is a special node called the root of the tree
-- The set of other nodes is partitioned into n>=0 classes A1, A2, ..., An, each class being a tree with root. The root of the tree is joined by edges to the roots of the trees A1, A2, ..., An.

PRIORITY QUEUE

 - An abstract data structure consisting of elements that have an associated value called a key or priority that carries the following operations:
-- Insert(Q,x): inserts element x into the priority queue Q;
-- ExtractMax(Q): extracts the maximum value element from the priority queue Q.

MAX-HEAP

 - A complete binary tree in which the value stored in any of its nodes is greater than or equal to the values stored in its child nodes.

MIN-HEAP

 - A complete binary tree in which the value stored in any of its nodes is less than or equal to the values stored in its child nodes.