Bubble-up (Node i ):Time = O(logn) use 4 insert Heapsort /* Heapify: */Equal(n) QuickSort Running time details
while (p(i ) exists) and (value(p(i)) < value(i)) { for i := n/2 downto 1
exchange values(i ) and value(p(i )); Bubble-down(i)
i ← p(i );} /* ExtractMax one at a time */
while (n > 1) {
Bubble-down (Node i ): Time:O(logn) use EMax Swap(A[n], A[1]);
while (i has children) { n--;
let j be the child of i with the largest value Bubble-down(1);}
if value(j) > value(i ) then
exchange values(i ) and value(j); QuickSortRecurseOnSmallerPart(int[] A, int left, int right): Rotations
i ← j ; int myLeft := left, myRight := right;
RandomPermute(A, n):
otherwise for i ← 1 to n while (myLeft < myRight) do
break;} exchange(A[i ], A[random(i , n)]) | int i := Partition(A, myLeft, myRight);
| if (i-myLeft) < (myRight - i) then
QuickSort(int[] A, int left, int right): | | QuickSortRecurseOnSmallerPart(A, myLeft, i-1);
if left < right | | myLeft = i+1
| else
int i := Partition(A, left, right); | | QuickSortRecurseOnSmallerPart(A, i+1, myRight);
QuickSort(A, left, i-1);
QuickSort(A, i+1, right); | | myRight = i-1
Partition(A, left, right): Theorem
pivot := A[right]; The height of an AVL tree with n nodes is O(log n).
i := left-1; Proof: What is the least number of nodes (nh) of an AVL-tree of height h?
for j := left to right Recurrence relation: ni = ni−1 + ni−2 + 1. Predecessor: at most right in leftsubtree
if A[j] <= pivot ni = Fi+3 – 1 = floor( feta^(i+3) / sqrt(5) ) + ½ - 1 Successor : at most left in rightsubtree
i := i+1 Therefore, ni = equal( feta^I ) Flooring and ceiling
swap(A[j], A[i]) Hence, n ≥ nh = equal(feta^I.) implies h = O(logn) 3/2 floor(1) ceiling (2)
return i; 5/2 floor(2) ceiling (3)
Running time of Partition: Extendable hashing: search 7/2 floor(3) ceiling (4)
Equal(right − left + 2). Summation equations
Given a key k, compute h(k) = a1a2 . . . aL.
Auxiliary Space: Equal(1).
◮ Probe block B(a1 . . . ad ).
◮ Perform a binary search to find all items in the block.
If the directly resides in internal memory, we have only a single memory
Priority queue sort block transfer.
for i ← 1 . . . n do
PQ.insert(A[i]);
for i ← n . . . 1 do Insert(x) is done as follows: ◮ Unsuccessful Search(x):
A[i] = PQ.extractMax(); ◮ Search for x to find the proper block to insert
◮ Computing the hash value h(x) takes Equal(1).
◮ If the block has space then done ◮ A list is searched to the end of the list.
◮ If the block is full (i.e. has already S keys) and k < d, perform ablock split: ◮ By uniform hashi

More
Less