Heaps

In a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C. The node at the “top” of the heap (with no parents) is called the root node.

Support of random access iterators is required to keep a heap structure internally at all times. This is done automatically by the container adaptor by automatically calling the algorithm functions make_heap, push_heap and pop_heap when needed. The standard container classes vector, deque and list fulfill these requirements. By default, if no container class is specified for a particular stack class instantiation, the standard container deque is used.

A heap is a useful data structure when it is necessary to repeatedly remove the object with the highest (or lowest) priority.

A beap, or bi-parental heap, is a data structure where a node usually has two parents

A B-heap is a binary heap implemented to keep subtrees in a single page

See Beap (bi-parental heap) and Heaps

Microbenchmarking for cache misses

Making a small part of the system make fewer cache misses means more hot cache is available for the rest of the system.

Trees

Trees are like a linked list but not just a straight line.
Fundamental rule: there is one path between nodes in a tree.
A binary tree has at most two child noes: known as the left and right children

Binary tree search

Sorted hierarchy of data
A root node
Left most node is the smallest, right most node is the largest
Adding nodes that already exist: add to the right (larger)

Terminology

Root / top / head node
Leaf / terminals nodes
Child / parent

Node traverals

Pre-order
In-order - left first, enumerates in sort order
Post-order

Implementation

Recursive or stack.

AVL tree

In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Lookup, insertion, and deletion all take O(log n) time in both the average and worst cases, where n is the number of nodes in the tree prior to the operation.

B-tree (binary tree)

A red–black tree is a kind of self-balancing binary search tree in computer science. Each node of the binary tree has an extra bit, and that bit is often interpreted as the color (red or black) of the node. These color bits are used to ensure the tree remains approximately balanced during insertions and deletions.

Balanced: all leaf nodes same time to travel from root
All nodes have the same capacity M
Inner and leaf nodes require minimum fill of m >= M/2
h = (m+1)^h
Typically a disk optimised data structure

Data structures