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
Tree types
- Geohash
- R-tree - rectangle tree
- M-tree - multidimensional tree
Bloom filter
A bloom filter tests whether an element is a member of a set.