Showing posts with label Algorithm. Show all posts
Showing posts with label Algorithm. Show all posts
Data Structure : Introduction of Non linear D.S.
In the first lesson of this section, we discussed the problem of representing relationships between employees at the XYZ company. Since these relationships are not linear, we could not adequately show the relationships using a linear data structure like a list or a stack. Instead, we needed something that looks more like a tree.
A tree is just one example of a nonlinear data structure. Two other examples are multidimensional arrays and graphs. In the next few lessons, we will examine these data structures to see how they are represented using the computer's linear memory. Remember that in the last lesson we saw that we could create a logical representation of a circular queue. Although the actual memory locations were just an array (a group of linear memory cells), we made them seem to be circular by wrapping our pointers around to the front of the array each time they reached the end. This example demonstrated that there are two ways of representing our data structure. The logical representation was a circle or a loop, while the physical representation was a simple linear array.
For each of the data structures we examine, we will look at a simple implementation for the data structure to see how it can be represented in physical memory. Then we will compare this physical representation with the logical representation of the data structure.
Data Structure : Infix, Postfix and Prefix
Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. It is easiest to demonstrate the differences by looking at examples of operators that take two operands.
- Infix notation: X + Y
- Operators are written in-between their operands. This is the usual way we write expressions. An expression such as
A * ( B + C ) / Dis usually taken to mean something like: "First add B and C together, then multiply the result by A, then divide by D to give the final answer."Infix notation needs extra information to make the order of evaluation of the operators clear: rules built into the language about operator precedence and associativity, and brackets( )to allow users to override these rules. For example, the usual rules for associativity say that we perform operations from left to right, so the multiplication by A is assumed to come before the division by D. Similarly, the usual rules for precedence say that we perform multiplication and division before we perform addition and subtraction.
- Postfix notation (also known as "Reverse Polish notation"): X Y +
- Operators are written after their operands. The infix expression given above is equivalent to
A B C + * D /
The order of evaluation of operators is always left-to-right, and brackets cannot be used to change this order. Because the "+" is to the left of the "*" in the example above, the addition must be performed before the multiplication.
Operators act on values immediately to the left of them. For example, the "+" above uses the "B" and "C". We can add (totally unnecessary) brackets to make this explicit:( (A (B C +) *) D /)
Thus, the "*" uses the two values immediately preceding: "A", and the result of the addition. Similarly, the "/" uses the result of the multiplication and the "D". - Prefix notation (also known as "Polish notation"): + X Y
- Operators are written before their operands. The expressions given above are equivalent to
/ * A + B C D
As for Postfix, operators are evaluated left-to-right and brackets are superfluous. Operators act on the two nearest values on the right. I have again added (totally unnecessary) brackets to make this clear:(/ (* A (+ B C) ) D)Although Prefix "operators are evaluated left-to-right", they use values to their right, and if these values themselves involve computations then this changes the order that the operators have to be evaluated in. In the example above, although the division is the first operator on the left, it acts on the result of the multiplication, and so the multiplication has to happen before the division (and similarly the addition has to happen before the multiplication).
Because Postfix operators use values to their left, any values involving computations will already have been calculated as we go left-to-right, and so the order of evaluation of the operators is not disrupted in the same way as in Prefix expressions.
In all three versions, the operands occur in the same order, and just the operators have to be moved to keep the meaning correct. (This is particularly important for asymmetric operators like subtraction and division:
A - B does not mean the same as B - A; the former is equivalent to A B - or - A B, the latter to B A - or- B A).
Examples:
| Infix | Postfix | Prefix | Notes |
|---|---|---|---|
A * B + C / D | A B * C D / + | + * A B / C D | multiply A and B, divide C by D, add the results |
A * (B + C) / D | A B C + * D / | / * A + B C D | add B and C, multiply by A, divide by D |
A * (B + C / D) | A B C D / + * | * A + B / C D | divide C by D, add B, multiply by A |
Converting between these notations
The most straightforward method is to start by inserting all the implicit brackets that show the order of evaluation e.g.:| Infix | Postfix | Prefix |
|---|---|---|
( (A * B) + (C / D) ) | ( (A B *) (C D /) +) | (+ (* A B) (/ C D) ) |
((A * (B + C) ) / D) | ( (A (B C +) *) D /) | (/ (* A (+ B C) ) D) |
(A * (B + (C / D) ) ) | (A (B (C D /) +) *) | (* A (+ B (/ C D) ) ) |
You can convert directly between these bracketed forms simply by moving the operator within the brackets e.g.
(X + Y) or (X Y +) or (+ X Y). Repeat this for all the operators in an expression, and finally remove any superfluous brackets.
You can use a similar trick to convert to and from parse trees - each bracketed triplet of an operator and its two operands (or sub-expressions) corresponds to a node of the tree. The corresponding parse trees are:
/ *
+ / \ / \
/ \ * D A +
/ \ / \ / \
* / A + B /
/ \ / \ / \ / \
A B C D B C C D
((A*B)+(C/D)) ((A*(B+C))/D) (A*(B+(C/D)))
Data Structure: Quick Sort
The basic version of quick sort algorithm was invented by C. A. R. Hoare in 1960 and formally introduced quick sort in 1962. It is used on the principle of divide-and-conquer. Quick sort is an algorithm of choice in many situations because it is not difficult to implement, it is a good "general purpose" sort and it consumes relatively fewer resources during execution.
Good points
- It is in-place since it uses only a small auxiliary stack.
- It requires only n log(n) time to sort n items.
- It has an extremely short inner loop
- This algorithm has been subjected to a thorough mathematical analysis, a very precise statement can be made about performance issues.
Bad Points
- It is recursive. Especially if recursion is not available, the implementation is extremely complicated.
- It requires quadratic (i.e., n2) time in the worst-case.
- It is fragile i.e., a simple mistake in the implementation can go unnoticed and cause it to perform badly.
Quick sort works by partitioning a given array A[p . . r] into two non-empty sub array A[p . . q] and A[q+1 . . r] such that every key in A[p . . q] is less than or equal to every key in A[q+1 . . r]. Then the two subarrays are sorted by recursive calls to Quick sort. The exact position of the partition depends on the given array and index q is computed as a part of the partitioning procedure.
QuickSort
- If p < r then
- q Partition (A, p, r)
- Recursive call to Quick Sort (A, p, q)
- Recursive call to Quick Sort (A, q + r, r)
Note that to sort entire array, the initial call Quick Sort (A, 1, length[A])
As a first step, Quick Sort chooses as pivot one of the items in the array to be sorted. Then array is then partitioned on either side of the pivot. Elements that are less than or equal to pivot will move toward the left and elements that are greater than or equal to pivot will move toward the right.
Partitioning the Array
Partitioning procedure rearranges the subarrays in-place.
PARTITION (A, p, r)
- x ← A[p]
- i ← p-1
- j ← r+1
- while TRUE do
- Repeat j ← j-1
- until A[j] ≤ x
- Repeat i ← i+1
- until A[i] ≥ x
- if i < j
- then exchange A[i] ↔ A[j]
- else return j
Partition selects the first key, A[p] as a pivot key about which the array will partitioned:
Keys ≤ A[p] will be moved towards the left .
Keys ≥ A[p] will be moved towards the right.
Keys ≥ A[p] will be moved towards the right.
The running time of the partition procedure is
(n) where n = r - p +1 which is the number of keys in the array.
Another argument that running time of PARTITION on a subarray of size
(n) is as follows: Pointer i and pointer j start at each end and move towards each other, conveying somewhere in the middle. The total number of times that i can be incremented and j can be decremented is therefore O(n). Associated with each increment or decrement there are O(1) comparisons and swaps. Hence, the total time is O(n).
Array of Same Elements
Since all the elements are equal, the "less than or equal" teat in lines 6 and 8 in the PARTITION (A, p, r) will always be true. this simply means that repeat loop all stop at once. Intuitively, the first repeat loop moves j to the left; the second repeat loop moves i to the right. In this case, when all elements are equal, each repeat loop moves i and j towards the middle one space. They meet in the middle, so q= Floor(p+r/2). Therefore, when all elements in the array A[p . . r] have the same value equal to Floor(p+r/2).
Performance of Quick Sort
The running time of quick sort depends on whether partition is balanced or unbalanced, which in turn depends on which elements of an array to be sorted are used for partitioning.
A very good partition splits an array up into two equal sized arrays. A bad partition, on other hand, splits an array up into two arrays of very different sizes. The worst partition puts only one element in one array and all other elements in the other array. If the partitioning is balanced, the Quick sort runs asymptotically as fast as merge sort. On the other hand, if partitioning is unbalanced, the Quick sort runs asymptotically as slow as insertion sort.
Best Case
The best thing that could happen in Quick sort would be that each partitioning stage divides the array exactly in half. In other words, the best to be a median of the keys in A[p . . r] every time procedure 'Partition' is called. The procedure 'Partition' always split the array to be sorted into two equal sized arrays.
If the procedure 'Partition' produces two regions of size n/2. the recurrence relation is then
T(n) = T(n/2) + T(n/2) +(n)
= 2T(n/2) +(n)
And from case 2 of Master theorem
T(n) =
(n lg n)
Worst case Partitioning
The worst-case occurs if given array A[1 . . n] is already sorted. The PARTITION (A, p, r) call always return p so successive calls to partition will split arrays of length n, n-1, n-2, . . . , 2 and running time proportional to n + (n-1) + (n-2) + . . . + 2 = [(n+2)(n-1)]/2 =
(n2). The worst-case also occurs if A[1 . . n] starts out in reverse order.
Randomized Quick Sort
In the randomized version of Quick sort we impose a distribution on input. This does not improve the worst-case running time independent of the input ordering.
In this version we choose a random key for the pivot. Assume that procedure Random (a, b) returns a random integer in the range [a, b); there are b-a+1 integers in the range and procedure is equally likely to return one of them. The new partition procedure, simply implemented the swap before actually partitioning.
RANDOMIZED_PARTITION (A, p, r)
i ← RANDOM (p, r)
Exchange A[p] ↔ A[i]
return PARTITION (A, p, r)
Now randomized quick sort call the above procedure in place of PARTITION
RANDOMIZED_QUICKSORT (A, p, r)
If p < r then
q ← RANDOMIZED_PARTITION (A, p, r)
RANDOMIZED_QUICKSORT (A, p,q)
RANDOMIZED_QUICKSORT (A, q+1,
r)
Like other randomized algorithms, RANDOMIZED_QUICKSORT has the property that no particular input elicits its worst-case behavior; the behavior of algorithm only depends on the random-number generator. Even intentionally, we cannot produce a bad input for RANDOMIZED_QUICKSORT unless we can predict generator will produce next.
Analysis of Quick sort
Worst-case
Let T(n) be the worst-case time for QUICK SORT on input size n. We have a recurrence
T(n) = max1≤q≤n-1 (T(q) + T(n-q)) +where q runs from 1 to n-1, since the partition produces two regions, each having size at least 1.(n) --------- 1
Now we guess that T(n) ≤ cn2 for some constant c.
Substituting our guess in equation 1.We get
Since the second derivative of expression q2 + (n-q)2 with respect to q is positive. Therefore, expression achieves a maximum over the range 1≤ q ≤ n -1 at one of the endpoints. This gives the bound max (q2 + (n- q)2)) 1 + (n -1)2 = n2 + 2(n -1).
T(n) = max1≤q≤n-1 (cq2 ) + c(n - q2)) +(n)
= c max (q2 + (n - q)2) +(n)
Continuing with our bounding of T(n) we get
T(n) ≤ c [n2 - 2(n-1)] +Since we can pick the constant so that the 2c(n -1) term dominates the(n)
= cn2 - 2c(n-1) +(n)
(n) term we have
T(n) ≤ cn2Thus the worst-case running time of quick sort is(n2).
Average-case Analysis
If the split induced by RANDOMIZED_PARTITION puts constant fraction of elements on one side of the partition, then the recurrence tree has depth(lgn) and
(n) work is performed at
(lg n) of these level. This is an intuitive argument why the average-case running time of RANDOMIZED_QUICKSORT is
(n lg n).
Let T(n) denotes the average time required to sort an array of n elements. A call to RANDOMIZED_QUICKSORT with a 1 element array takes a constant time, so we have T(1) =(1).
After the split RANDOMIZED_QUICKSORT calls itself to sort two subarrays. The average time to sort an arrayA[1 . . q] is T[q] and the average time to sort an array A[q+1 . . n] is T[n-q]. We have
T(n) = 1/n (T(1) + T(n-1) + n-1∑q=1 T(q) + T(n-q))) +We know from worst-case analysis(n) ----- 1
Solve the above recurrence using substitution method. Assume inductively that T(n) ≤ anlgn + b for some constants a > 0 and b > 0.T(1) =(1) and T(n -1) = O(n2)
T(n) = 1/n ((1) + O(n2)) + 1/n n-1∑q=1 (r(q) + T(n - q)) +
(n)
= 1/n n-1∑q=1(T(q) + T(n - q)) +(n) ------- 2
= 1/n[2 n-1∑k=1(T(k)] +(n)
= 2/n n-1∑k=1(T(k) +(n) --------- 3
If we can pick 'a' and 'b' large enough so that n lg n + b > T(1). Then for n > 1, we have
At this point we are claiming thatT(n) ≥ n-1∑k=1 2/n (aklgk + b) +(n)
= 2a/n n-1∑k=1 klgk - 1/8(n2) + 2b/n (n -1) +(n) ------- 4
Stick this claim in the equation 4 above and we getn-1∑k=1 klgk ≤ 1/2 n2 lgn - 1/8(n2)
In the above equation, we see thatT(n) ≤ 2a/n [1/2 n2 lgn - 1/8(n2)] + 2/n b(n -1) +(n)
≤ anlgn - an/4 + 2b +(n) ---------- 5
(n) + b and an/4 are polynomials and we certainly can choose 'a' large enough so that an/4 dominates
(n) + b.
We conclude that QUICKSORT's average running time is(n lg(n)).
Conclusion
Quick sort is an in place sorting algorithm whose worst-case running time is
(n2) and expected running time is
(n lg n) where constants hidden in
(n lg n) are small.
Implementation
void quickSort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right)
{
while ((numbers[right] >= pivot) && (left < right))
right--;
if (left != right)
{
numbers[left] = numbers[right];
left++;
}
while ((numbers[left] <= pivot) && (left < right))
left++;
if (left != right)
{
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if (left < pivot)
q_sort(numbers, left, pivot-1);
if (right > pivot)
q_sort(numbers, pivot+1, right);
}
Data Structure:Merge Sort
Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with subproblems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through subproblems.
To sort A[p .. r]:
1. Divide Step
If a given array A has zero or one element, simply return; it is already sorted. Otherwise, split A[p .. r] into two subarrays A[p.. q] and A[q + 1 .. r], each containing about half of the elements of A[p .. r]. That is, q is the halfway point of A[p .. r].
2. Conquer Step
Conquer by recursively sorting the two subarrays A[p .. q] and A[q + 1 .. r].
3. Combine Step
Combine the elements back in A[p .. r] by merging the two sorted subarrays A[p .. q] and A[q + 1 .. r] into a sorted sequence. To accomplish this step, we will define a procedure MERGE (A, p, q, r).
Note that the recursion bottoms out when the subarray has just one element, so that it is trivially sorted.
Algorithm: Merge Sort
To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (A, 1, n).
MERGE-SORT (A, p, r)
1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.
Example: Bottom-up view of the above procedure for n = 8.
Merging
What remains is the MERGE procedure. The following is the input and output of the MERGE procedure.
INPUT: Array A and indices p, q, r such that p ≤ q ≤ r and subarray A[p .. q] is sorted and subarray A[q + 1 .. r] is sorted. By restrictions on p, q, r, neither subarray is empty.
OUTPUT: The two subarrays are merged into a single sorted subarray in A[p .. r].
We implement it so that it takes Θ(n) time, where n = r − p + 1, which is the number of elements being merged.
Idea Behind Linear Time Merging
Think of two piles of cards, Each pile is sorted and placed face-up on a table with the smallest cards on top. We will merge these into a single sorted pile, face-down on the table.
A basic step:
- Choose the smaller of the two top cards.
- Remove it from its pile, thereby exposing a new top card.
- Place the chosen card face-down onto the output pile.
- Repeatedly perform basic steps until one input pile is empty.
- Once one input pile empties, just take the remaining input pile and place it face-down onto the output pile.
Each basic step should take constant time, since we check just the two top cards. There are at most n basic steps, since each basic step removes one card from the input piles, and we started with n cards in the input piles. Therefore, this procedure should take Θ(n) time.
Now the question is do we actually need to check whether a pile is empty before each basic step?
The answer is no, we do not. Put on the bottom of each input pile a special sentinel card. It contains a special value that we use to simplify the code. We use ∞, since that's guaranteed to lose to any other value. The only way that ∞ cannot lose is when both piles have ∞ exposed as their top cards. But when that happens, all the nonsentinel cards have already been placed into the output pile. We know in advance that there are exactly r − p + 1 nonsentinel cards so stop once we have performed r − p + 1 basic steps. Never a need to check for sentinels, since they will always lose. Rather than even counting basic steps, just fill up the output array from index p up through and including index r .
The answer is no, we do not. Put on the bottom of each input pile a special sentinel card. It contains a special value that we use to simplify the code. We use ∞, since that's guaranteed to lose to any other value. The only way that ∞ cannot lose is when both piles have ∞ exposed as their top cards. But when that happens, all the nonsentinel cards have already been placed into the output pile. We know in advance that there are exactly r − p + 1 nonsentinel cards so stop once we have performed r − p + 1 basic steps. Never a need to check for sentinels, since they will always lose. Rather than even counting basic steps, just fill up the output array from index p up through and including index r .
The pseudocode of the MERGE procedure is as follow:
MERGE (A, p, q, r )
1. n1 ← q − p + 1
2. n2 ← r − q
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4. FOR i ← 1 TO n1
5. DO L[i] ← A[p + i − 1]
6. FOR j ← 1 TO n2
7. DO R[j] ← A[q + j ]
8. L[n1 + 1] ← ∞
9. R[n2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. FOR k ← p TO r
13. DO IF L[i ] ≤ R[ j]
14. THEN A[k] ← L[i]
15. i ← i + 1
16. ELSE A[k] ← R[j]
17. j ← j + 1
2. n2 ← r − q
3. Create arrays L[1 . . n1 + 1] and R[1 . . n2 + 1]
4. FOR i ← 1 TO n1
5. DO L[i] ← A[p + i − 1]
6. FOR j ← 1 TO n2
7. DO R[j] ← A[q + j ]
8. L[n1 + 1] ← ∞
9. R[n2 + 1] ← ∞
10. i ← 1
11. j ← 1
12. FOR k ← p TO r
13. DO IF L[i ] ≤ R[ j]
14. THEN A[k] ← L[i]
15. i ← i + 1
16. ELSE A[k] ← R[j]
17. j ← j + 1
Example [from CLRS-Figure 2.3]: A call of MERGE(A, 9, 12, 16). Read the following figure row by row. That is how we have done in the class.
- The first part shows the arrays at the start of the "for k ← p to r" loop, where A[p . . q] is copied into L[1 . . n1] and A[q + 1 . . r ] is
copied into R[1 . . n2]. - Succeeding parts show the situation at the start of successive iterations.
- Entries in A with slashes have had their values copied to either L or R and have not had a value copied back in yet. Entries in L and R with slashes have been copied back into A.
- The last part shows that the subarrays are merged back into A[p . . r], which is now sorted, and that only the sentinels (∞) are exposed in the arrays L and R.]
Running Time
The first two for loops (that is, the loop in line 4 and the loop in line 6) take Θ(n1 + n2) = Θ(n) time. The last for loop (that is, the loop in line 12) makes n iterations, each taking constant time, for Θ(n) time. Therefore, the total running time is Θ(n).
Analyzing Merge Sort
For simplicity, assume that n is a power of 2 so that each divide step yields two subproblems, both of size exactly n/2.
The base case occurs when n = 1.
When n ≥ 2, time for merge sort steps:
- Divide: Just compute q as the average of p and r, which takes constant time i.e. Θ(1).
- Conquer: Recursively solve 2 subproblems, each of size n/2, which is 2T(n/2).
- Combine: MERGE on an n-element subarray takes Θ(n) time.
Summed together they give a function that is linear in n, which is Θ(n). Therefore, the recurrence for merge sort running time is
Solving the Merge Sort Recurrence
By the master theorem in CLRS-Chapter 4 (page 73), we can show that this recurrence has the solution
T(n) = Θ(n lg n).
Reminder: lg n stands for log2 n.
Compared to insertion sort [Θ(n2) worst-case time], merge sort is faster. Trading a factor of n for a factor of lg n is a good deal. On small inputs, insertion sort may be faster. But for large enough inputs, merge sort will always be faster, because its running time grows more slowly than insertion sorts.
Recursion Tree
We can understand how to solve the merge-sort recurrence without the master theorem. There is a drawing of recursion tree on page 35 in CLRS, which shows successive expansions of the recurrence.
The following figure (Figure 2.5b in CLRS) shows that for the original problem, we have a cost of cn, plus the two subproblems, each costing T (n/2).
The following figure (Figure 2.5c in CLRS) shows that for each of the size-n/2 subproblems, we have a cost of cn/2, plus two subproblems, each costing T (n/4).
The following figure (Figure: 2.5d in CLRS) tells to continue expanding until the problem sizes get down to 1.
In the above recursion tree, each level has cost cn.
- The top level has cost cn.
- The next level down has 2 subproblems, each contributing cost cn/2.
- The next level has 4 subproblems, each contributing cost cn/4.
- Each time we go down one level, the number of subproblems doubles but the cost per subproblem halves. Therefore, cost per level stays the same.
The height of this recursion tree is lg n and there are lg n + 1 levels.
Mathematical Induction
We use induction on the size of a given subproblem n.
Base case: n = 1
Implies that there is 1 level, and lg 1 + 1 = 0 + 1 = 1.
Inductive Step
Our inductive hypothesis is that a tree for a problem size of 2i has lg 2i + 1 = i +1 levels. Because we assume that the problem size is a power of 2, the next problem size up after 2i is 2i + 1. A tree for a problem size of 2i + 1 has one more level than the size-2i tree implying i + 2 levels. Since lg 2i + 1 = i + 2, we are done with the inductive argument.
Total cost is sum of costs at each level of the tree. Since we have lg n +1 levels, each costing cn, the total cost is
cn lg n + cn.
Ignore low-order term of cn and constant coefÞcient c, and we have,
Θ(n lg n)
which is the desired result.
Implementation
void mergeSort(int numbers[], int temp[], int array_size)
{
m_sort(numbers, temp, 0, array_size - 1);}
void m_sort(int numbers[], int temp[], int left, int right){
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
m_sort(numbers, temp, 0, array_size - 1);}
void m_sort(int numbers[], int temp[], int left, int right){
int mid;
if (right > left)
{
mid = (right + left) / 2;
m_sort(numbers, temp, left, mid);
m_sort(numbers, temp, mid+1, right);
merge(numbers, temp, left, mid+1, right);
}
}
void merge(int numbers[], int temp[], int left, int mid, int right)
{
int i, left_end, num_elements, tmp_pos;
left_end = mid - 1;
tmp_pos = left;
num_elements = right - left + 1;
while ((left <= left_end) && (mid <= right))
{
if (numbers[left] <= numbers[mid])
{
temp[tmp_pos] = numbers[left];
tmp_pos = tmp_pos + 1;
left = left +1;
}
else
{
temp[tmp_pos] = numbers[mid];
tmp_pos = tmp_pos + 1;
mid = mid + 1;
}
}
while (left <= left_end)
{
temp[tmp_pos] = numbers[left];
left = left + 1;
tmp_pos = tmp_pos + 1;
}
while (mid <= right)
{
temp[tmp_pos] = numbers[mid];
mid = mid + 1;
tmp_pos = tmp_pos + 1;
}
for (i = 0; i <= num_elements; i++)
{
numbers[right] = temp[right];
right = right - 1;
}
}
Data Structure : Heap Sort
The binary heap data structures is an array that can be viewed as a complete binary tree. Each node of the binary tree corresponds to an element of the array. The array is completely filled on all levels except possibly lowest.
We represent heaps in level order, going from left to right. The array corresponding to the heap above is [25, 13, 17, 5, 8, 3].
The root of the tree A[1] and given index i of a node, the indices of its parent, left child and right child can be computed
PARENT (i)
return floor(i/2)
LEFT (i)
return 2i
RIGHT (i)
return 2i + 1
Let's try these out on a heap to make sure we believe they are correct. Take this heap,
which is represented by the array [20, 14, 17, 8, 6, 9, 4, 1].
We'll go from the 20 to the 6 first. The index of the 20 is 1. To find the index of the left child, we calculate 1 * 2 = 2. This takes us (correctly) to the 14. Now, we go right, so we calculate 2 * 2 + 1 = 5. This takes us (again, correctly) to the 6.
Now let's try going from the 4 to the 20. 4's index is 7. We want to go to the parent, so we calculate 7 / 2 = 3, which takes us to the 17. Now, to get 17's parent, we calculate 3 / 2 = 1, which takes us to the 20.
Heap Property
In a heap, for every node i other than the root, the value of a node is greater than or equal (at most) to the value of its parent.
A[PARENT (i)] ≥ A[i]
Thus, the largest element in a heap is stored at the root.
Following is an example of Heap:
By the definition of a heap, all the tree levels are completely filled except possibly for the lowest level, which is filled from the left up to a point. Clearly a heap of height h has the minimum number of elements when it has just one node at the lowest level. The levels above the lowest level form a complete binary tree of height h -1 and 2h -1 nodes. Hence the minimum number of nodes possible in a heap of height h is 2h. Clearly a heap of height h, has the maximum number of elements when its lowest level is completely filled. In this case the heap is a complete binary tree of height h and hence has 2h+1 -1 nodes.
Following is not a heap, because it only has the heap property - it is not a complete binary tree. Recall that to be complete, a binary tree has to fill up all of its levels with the possible exception of the last one, which must be filled in from the left side.
Height of a node
We define the height of a node in a tree to be a number of edges on the longest simple downward path from a node to a leaf.
Height of a tree
The number of edges on a simple downward path from a root to a leaf. Note that the height of a tree with n node is
lg n
which is
(lgn). This implies that an n-element heap has height
lg n
In order to show this let the height of the n-element heap be h. From the bounds obtained on maximum and minimum number of elements in a heap, we get
2h ≤ n ≤ 2h+1-1
Where n is the number of elements in a heap.
2h ≤ n ≤ 2h+1
Taking logarithms to the base 2
h ≤ lgn ≤ h +1
It follows that h =
lgn
.
We known from above that largest element resides in root, A[1]. The natural question to ask is where in a heap might the smallest element resides? Consider any path from root of the tree to a leaf. Because of the heap property, as we follow that path, the elements are either decreasing or staying the same. If it happens to be the case that all elements in the heap are distinct, then the above implies that the smallest is in a leaf of the tree. It could also be that an entire subtree of the heap is the smallest element or indeed that there is only one element in the heap, which in the smallest element, so the smallest element is everywhere. Note that anything below the smallest element must equal the smallest element, so in general, only entire subtrees of the heap can contain the smallest element.
Inserting Element in the Heap
Suppose we have a heap as follows
Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.
Let's suppose we want to add a node with key 15 to the heap. First, we add the node to the tree at the next spot available at the lowest level of the tree. This is to ensure that the tree remains complete.
Now we do the same thing again, comparing the new node to its parent. Since 14 < 15, we have to do another swap:
Now we are done, because 15
20.
Four basic procedures on heap are
- Heapify, which runs in O(lg n) time.
- Build-Heap, which runs in linear time.
- Heap Sort, which runs in O(n lg n) time.
- Extract-Max, which runs in O(lg n) time.
Maintaining the Heap Property
Heapify is a procedure for manipulating heap data structures. It is given an array A and index i into the array. The subtree rooted at the children of A[i] are heap but node A[i] itself may possibly violate the heap property i.e., A[i] < A[2i] or A[i] < A[2i +1]. The procedure 'Heapify' manipulates the tree rooted at A[i] so it becomes a heap. In other words, 'Heapify' is let the value at A[i] "float down" in a heap so that subtree rooted at index i becomes a heap.
Outline of Procedure Heapify
Heapify picks the largest child key and compare it to the parent key. If parent key is larger than heapify quits, otherwise it swaps the parent key with the largest child key. So that the parent is now becomes larger than its children.
It is important to note that swap may destroy the heap property of the subtree rooted at the largest child node. If this is the case, Heapify calls itself again using largest child node as the new root.
Heapify (A, i)
- l ← left [i]
- r ← right [i]
- if l ≤ heap-size [A] and A[l] > A[i]
- then largest ← l
- else largest ← i
- if r ≤ heap-size [A] and A[i] > A[largest]
- then largest ← r
- if largest ≠ i
- then exchange A[i] ↔ A[largest]
- Heapify (A, largest)
Analysis
If we put a value at root that is less than every value in the left and right subtree, then 'Heapify' will be called recursively until leaf is reached. To make recursive calls traverse the longest path to a leaf, choose value that make 'Heapify' always recurse on the left child. It follows the left branch when left child is greater than or equal to the right child, so putting 0 at the root and 1 at all other nodes, for example, will accomplished this task. With such values 'Heapify' will called h times, where h is the heap height so its running time will beθ(h) (since each call does
(1) work), which is
(lgn). Since we have a case in which Heapify's running time
(lg n), its worst-case running time is Ω(lgn).
Example of Heapify
Suppose we have a complete binary tree somewhere whose subtrees are heaps. In the following complete binary tree, the subtrees of 6 are heaps:
The Heapify procedure alters the heap so that the tree rooted at 6's position is a heap. Here's how it works. First, we look at the root of our tree and its two children.
We then determine which of the three nodes is the greatest. If it is the root, we are done, because we have a heap. If not, we exchange the appropriate child with the root, and continue recursively down the tree. In this case, we exchange 6 and 8, and continue.
Now, 7 is greater than 6, so we exchange them.
We are at the bottom of the tree, and can't continue, so we terminate.
Building a Heap
We can use the procedure 'Heapify' in a bottom-up fashion to convert an array A[1 . . n] into a heap. Since the elements in the subarray A[
n/2
+1 . . n] are all leaves, the procedure BUILD_HEAP goes through the remaining nodes of the tree and runs 'Heapify' on each one. The bottom-up order of processing node guarantees that the subtree rooted at children are heap before 'Heapify' is run at their parent.
BUILD_HEAP (A)
- heap-size (A) ← length [A]
- For i ← floor(length[A]/2) down to 1 do
- Heapify (A, i)
We can build a heap from an unordered array in linear time.
Heap Sort Algorithm
The heap sort combines the best of both merge sort and insertion sort. Like merge sort, the worst case time of heap sort is O(n log n) and like insertion sort, heap sort sorts in-place. The heap sort algorithm starts by using procedure BUILD-HEAP to build a heap on the input array A[1 . . n]. Since the maximum element of the array stored at the root A[1], it can be put into its correct final position by exchanging it with A[n] (the last element in A). If we now discard node n from the heap than the remaining elements can be made into heap. Note that the new element at the root may violate the heap property. All that is needed to restore the heap property.
HEAPSORT (A)
- BUILD_HEAP (A)
- for i ← length (A) down to 2 do
exchange A[1] ↔ A[i]
heap-size [A] ← heap-size [A] - 1
Heapify (A, 1)
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD_HEAP takes time O(n) and each of the n -1 calls to Heapify takes time O(lg n).
Now we show that there are at most én/2h+1ù nodes of height h in any n-element heap. We need two observations to show this. The first is that if we consider the set of nodes of height h, they have the property that the subtree rooted at these nodes are disjoint. In other words, we cannot have two nodes of height h with one being an ancestor of the other. The second property is that all subtrees are complete binary trees except for one subtree. Let Xh be the number of nodes of height h. Since Xh-1 o ft hese subtrees are full, they each contain exactly 2h+1 -1 nodes. One of the height h subtrees may not full, but contain at least 1 node at its lower level and has at least2h nodes. The exact count is 1+2+4+ . . . + 2h+1 + 1 = 2h. The remaining nodes have height strictly more than h. To connect all subtrees rooted at node of height h., there must be exactly Xh -1 such nodes. The total of nodes is at least
(Xh-1)(2h+1 + 1) + 2h + Xh-1 which is at most n.
Simplifying gives
Xh ≤ n/2h+1 + 1/2.
In the conclusion, it is a property of binary trees that the number of nodes at any level is half of the total number of nodes up to that level. The number of leaves in a binary heap is equal to n/2, where n is the total number of nodes in the tree, is even and
n/2
whenn is odd. If these leaves are removed, the number of new leaves will be
lg(n/2/2
or
n/4
. If this process is continued for h levels the number of leaves at that level will be
n/2h+1
.
Implementation
void heapSort(int numbers[], int array_size)
{
int i, temp;
for (i = (array_size / 2)-1; i >= 0; i--)
siftDown(numbers, i, array_size);
for (i = array_size-1; i >= 1; i--)
{
temp = numbers[0];
numbers[0] = numbers[i];
numbers[i] = temp;
siftDown(numbers, 0, i-1);
}
}
void siftDown(int numbers[], int root, int bottom)
{
int done, maxChild, temp;
done = 0;
while ((root*2 <= bottom) && (!done))
{
if (root*2 == bottom)
maxChild = root * 2;
else if (numbers[root * 2] > numbers[root * 2 + 1])
maxChild = root * 2;
else
maxChild = root * 2 + 1;
if (numbers[root] < numbers[maxChild])
{
temp = numbers[root];
numbers[root] = numbers[maxChild];
numbers[maxChild] = temp;
root = maxChild;
}
else
done = 1;
}
}
Subscribe to:
Posts
(
Atom
)