lg N
.Array representation of a heap-ordered complete binary tree.
Heap-ordered binary tree.
Largest key is a[1], which is root of binary tree.
Can use array indices to move through tree.
Parent of node at k is at k/2.
Children of node at k are at 2k and 2k+1.
Insertion in a heap
Add node at end, then swim it up.
1 | private void swim(int k) { |
Delete the maximum in a heap
Exchange root with node at end, then sink it down.
1 | private void sink(int k) { |
Step 1: Build heap using bottom-up method.
1 | for (int k = N/2; k >= 1; k--) |
N
is just used to count
Step 2: Remove the maximum, one at a time. exchange the first element(maximum one) to the end, then sink the first element.
1 | while (N > 1) { |
N
is just used to countKey-value pair abstraction.
APIs
Ordered APIs
A BST is a binary tree in symmetric order.
A Node is comprised of four fields:
Search. If less, go left; if greater, go right; if equal, search hit.
Insert. If less, go left; if greater, go right; if null, insert.
Get. Return value corresponding to given key, or null if no such key.
Put. Associate value with key.
Different tree shapes
If N distinct keys are inserted into a BST in random order, the expected number of compares for a search/insert is ~ 2 ln N
.
Minimum. Smallest key in table.
Maximum. Largest key in table.
Floor. Largest key ≤ a given key.
Ceiling. Smallest key ≥ a given key.
null
.S
, E
and X
.G
< S
, so still null
. All of the right of S
should be bigger that S
, so we continue check the left side E
, A
and R
.E
< G
, so E
is a candidate. All of the left side of E
should be less that E
, So we continue check the right side of E
: R
, H
and null
.R
> G
, So the left side of R
: H
H
> G
, and H
is the leaf. So E
is the answer.Counts
Rank
Inorder traversal (Iteration)
To delete a node with key k: search for node t containing key k.
Case 0. [0 children]
Delete t by setting parent link to null.
Case 1. [1 child]
Delete t by replacing parent link.
Case 2. [2 children]
analysis