s14.ps

来自「c programming pearls answer」· PS 代码 · 共 1,353 行 · 第 1/2 页

20 H f
(The Code)1 882 1 720 4334 t
20 CW f
(void siftup\(n\))1 1680 1 864 4589 t
( > 0 && heap\(1, n-1\))5 2400(pre n)1 720 2 1824 4784 t
(post heap\(1, n\))2 1800 1 1824 4979 t
(i = n)2 600 1 1344 5174 t
(loop)1344 5369 w
(/* invariant: heap\(1, n\) except)4 3720 1 1824 5564 t
(between i and its parent */)5 3240 1 2304 5759 t
(if i == 1)3 1080 1 1824 5954 t
(break)2304 6149 w
(p = i / 2)4 1080 1 1824 6344 t
(if x[p] <= x[i])3 1800 1 1824 6539 t
(break)2304 6734 w
(swap\(p, i\))1 1200 1 1824 6929 t
(i = p)2 600 1 1824 7124 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-4)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 58 -1 583 726
%%EndPage: 4 4
%%Page: 5 5
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
5 pagesetup
20 H f
(The siftdown Function)2 1964 1 2078 960 t
(The Goal)1 826 1 720 1488 t
20 HI f
(x)1008 1896 w
20 H f
([ 2)1 184 1 1124 1896 t
20 HI f
(.)1324 1896 w
20 H f
(.)1380 1896 w
20 HI f
(n)1452 1896 w
20 H f
(] is a heap; sift)4 1296 1 1580 1896 t
20 HI f
(x)2932 1896 w
20 H f
( down, swapping with)3 1908([ 1 ])2 256 2 3048 1896 t
(the lesser child)2 1338 1 1008 2136 t
(Inserting 18)1 1050 1 720 2544 t
16 H f
(18)1450 2979 w
(20)1018 3231 w
1501 2998 1108 3120 Dl
(15)1882 3231 w
1579 2998 1972 3120 Dl
(29)802 3483 w
1069 3250 892 3372 Dl
(23)1234 3483 w
1147 3250 1324 3372 Dl
(17)1666 3483 w
1933 3250 1756 3372 Dl
(22)2098 3483 w
2011 3250 2188 3372 Dl
(35)694 3735 w
853 3502 784 3624 Dl
(40)910 3735 w
931 3502 1000 3624 Dl
(26)1126 3735 w
1285 3502 1216 3624 Dl
(51)1342 3735 w
1363 3502 1432 3624 Dl
(19)1558 3735 w
1717 3502 1648 3624 Dl
1467 2941 146 146 De
(15)3178 2979 w
(20)2746 3231 w
3229 2998 2836 3120 Dl
(18)3610 3231 w
3307 2998 3700 3120 Dl
(29)2530 3483 w
2797 3250 2620 3372 Dl
(23)2962 3483 w
2875 3250 3052 3372 Dl
(17)3394 3483 w
3661 3250 3484 3372 Dl
(22)3826 3483 w
3739 3250 3916 3372 Dl
(35)2422 3735 w
2581 3502 2512 3624 Dl
(40)2638 3735 w
2659 3502 2728 3624 Dl
(26)2854 3735 w
3013 3502 2944 3624 Dl
(51)3070 3735 w
3091 3502 3160 3624 Dl
(19)3286 3735 w
3445 3502 3376 3624 Dl
3627 3193 146 146 De
(15)4906 2979 w
(20)4474 3231 w
4957 2998 4564 3120 Dl
(17)5338 3231 w
5035 2998 5428 3120 Dl
(29)4258 3483 w
4525 3250 4348 3372 Dl
(23)4690 3483 w
4603 3250 4780 3372 Dl
(18)5122 3483 w
5389 3250 5212 3372 Dl
(22)5554 3483 w
5467 3250 5644 3372 Dl
(35)4150 3735 w
4309 3502 4240 3624 Dl
(40)4366 3735 w
4387 3502 4456 3624 Dl
(26)4582 3735 w
4741 3502 4672 3624 Dl
(51)4798 3735 w
4819 3502 4888 3624 Dl
(19)5014 3735 w
5173 3502 5104 3624 Dl
5139 3445 146 146 De
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-5)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 58 -1 583 726
%%EndPage: 5 5
%%Page: 6 6
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
6 pagesetup
18 H f
(siftdown code)1 1106 1 2507 960 t
20 CW f
(void siftdown\(n\))1 1920 1 720 1543 t
( n\) && n >= 0)5 1560(pre heap\(2,)1 1560 2 1680 1778 t
( n\))1 360(post heap\(1,)1 1560 2 1680 2013 t
(i = 1)2 600 1 1200 2248 t
(loop)1200 2483 w
(/* inv: heap\(1, n\) except between)5 3960 1 1680 2718 t
(i and its 0, 1 or 2 kids */)8 3240 1 2160 2953 t
(c = 2*i)2 840 1 1680 3188 t
(if c > n)3 960 1 1680 3423 t
(break)2160 3658 w
(/* c is the left child of i */)8 3600 1 1680 3893 t
(if c+1 <= n)3 1320 1 1680 4128 t
(/* c+1 is the right child of i */)8 3960 1 2160 4363 t
(if x[c+1] < x[c])3 1920 1 2160 4598 t
(c++)2640 4833 w
(/* c is the lesser child of i */)8 3840 1 1680 5068 t
(if x[i] <= x[c])3 1800 1 1680 5303 t
(break)2160 5538 w
(swap\(c, i\))1 1200 1 1680 5773 t
(i = c)2 600 1 1680 6008 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-6)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 622 724
%%EndPage: 6 6
%%Page: 7 7
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
7 pagesetup
20 H f
(Priority Queues)1 1382 1 2369 960 t
(The Abstract Data Type)3 2120 1 720 1488 t
(Operations on \(initially empty\) set)4 2976 1 1008 1896 t
20 HI f
(S)4040 1896 w
20 H f
(.)4174 1896 w
20 CW f
(void insert\(t\))1 1680 1 1008 2191 t
( < maxsize)2 1200(pre |S|)1 960 2 1248 2426 t
(post current S = original S)5 3240 1 1248 2661 t
20 S f
(\310)4608 2661 w
20 CW f
({t})4882 2661 w
(int extractmin\(\))1 1920 1 1008 3131 t
( > 0)2 480(pre |S|)1 960 2 1248 3366 t
(post original S = current S)5 3240 1 1248 3601 t
20 S f
(\310)4608 3601 w
20 CW f
({result})4882 3601 w
(&& result = min\(original S\))4 3240 1 1848 3836 t
20 H f
(Implementations)720 4304 w
18 S f
(_ __________________________________________________)1 4531 1 794 4474 t
(_ __________________________________________________)1 4531 1 794 4494 t
18 H f
(R)3291 4724 w
16 H f
(UN)3421 4724 w
18 H f
(T)3701 4724 w
16 H f
(IMES)3811 4724 w
18 S f
(_ ____________________________________)1 3290 1 2035 4784 t
18 H f
(S)847 4874 w
16 H f
(TRUCTURE)968 4874 w
18 H f
(1)2237 5024 w
18 HI f
(insert)2388 5024 w
18 H f
(1)3166 5024 w
18 HI f
(extractmin n)1 1283 1 3317 5024 t
18 H f
(of each)1 594 1 4650 5024 t
18 S f
(_ __________________________________________________)1 4531 1 794 5084 t
18 H f
(Sorted Seq)1 906 1 794 5324 t
18 HI f
(O)2331 5324 w
18 H f
(\()2486 5324 w
18 HI f
(n)2560 5324 w
18 H f
(\))2676 5324 w
18 HI f
(O)3455 5324 w
18 H f
(\( 1 \))2 249 1 3610 5324 t
18 HI f
(O)4607 5324 w
18 H f
(\()4762 5324 w
18 HI f
(n)4836 5324 w
15 H f
(2)4962 5252 w
18 H f
(\))5076 5324 w
(Heaps)794 5564 w
18 HI f
(O)2170 5564 w
18 H f
(\( log)1 316 1 2325 5564 t
18 HI f
(n)2721 5564 w
18 H f
(\))2837 5564 w
18 HI f
(O)3294 5564 w
18 H f
(\( log)1 316 1 3449 5564 t
18 HI f
(n)3845 5564 w
18 H f
(\))3961 5564 w
18 HI f
(O)4418 5564 w
18 H f
(\()4573 5564 w
18 HI f
(n)4647 5564 w
18 H f
(log)4828 5564 w
18 HI f
(n)5150 5564 w
18 H f
(\))5266 5564 w
(Unsorted Seq)1 1106 1 794 5804 t
18 HI f
(O)2331 5804 w
18 H f
(\( 1 \))2 249 1 2486 5804 t
18 HI f
(O)3455 5804 w
18 H f
(\()3610 5804 w
18 HI f
(n)3684 5804 w
18 H f
(\))3800 5804 w
18 HI f
(O)4607 5804 w
18 H f
(\()4762 5804 w
18 HI f
(n)4836 5804 w
15 H f
(2)4962 5732 w
18 H f
(\))5076 5804 w
18 S f
( \347)1 -3290(_ __________________________________________________)1 4531 2 794 5864 t
(\347)2035 5754 w
(\347)2035 5574 w
(\347)2035 5394 w
(\347)2035 5214 w
(\347)2035 5034 w
(\347)2035 4854 w
(\347)2035 4674 w
(\347)3031 5864 w
(\347)3031 5684 w
(\347)3031 5504 w
(\347)3031 5324 w
(\347)3031 5144 w
(\347)3031 4964 w
(\347)4283 5864 w
(\347)4283 5684 w
(\347)4283 5504 w
(\347)4283 5324 w
(\347)4283 5144 w
(\347)4283 4964 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-7)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 594 726
%%EndPage: 7 7
%%Page: 8 8
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
8 pagesetup
20 H f
(Heap Implementation of Priority Queues)4 3570 1 1275 960 t
20 CW f
(void insert\(t\))1 1680 1 720 1543 t
(if n >= maxsize)3 1800 1 1200 1778 t
(/* report error */)3 2160 1 1680 2013 t
(n++)1200 2248 w
(x[n] = t)2 960 1 1200 2483 t
(/* heap\(1, n-1\) */)3 2160 1 1200 2718 t
(siftup\(n\))1200 2953 w
(/* heap\(1, n\) */)3 1920 1 1200 3188 t
(int extractmin\(\))1 1920 1 720 3658 t
(if n < 1)3 960 1 1200 3893 t
(/* report error */)3 2160 1 1680 4128 t
(t = x[1])2 960 1 1200 4363 t
(x[1] = x[n--])2 1560 1 1200 4598 t
(/* heap\(2, n\) */)3 1920 1 1200 4833 t
(siftdown\(n\))1200 5068 w
(/* heap\(1, n\) */)3 1920 1 1200 5303 t
(return t)1 960 1 1200 5538 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-8)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 8 8
%%Page: 9 9
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
9 pagesetup
20 H f
(The Complete C++ Class)3 2248 1 1936 960 t
14 CW f
(template<class T>)1 1428 1 720 1295 t
(class priqueue {)2 1344 1 720 1450 t
(private:)720 1605 w
(int n, maxsize;)2 1260 1 1056 1760 t
(T *x;)1 420 1 1056 1915 t
(void swap\(int i, int j\))4 1932 1 1056 2070 t
( t = x[i]; x[i] = x[j]; x[j] = t; })10 2940({ T)1 420 2 1056 2225 t
(public:)720 2457 w
(priqueue\(int m\))1 1260 1 1056 2612 t
( = m;)2 420({ maxsize)1 924 2 1056 2767 t
(x = new T[maxsize+1];)3 1764 1 1392 2922 t
(n = 0;)2 504 1 1392 3077 t
(})1056 3232 w
(void insert\(T t\))2 1344 1 1056 3464 t
( i, p;)2 504({ int)1 588 2 1056 3619 t
(x[++n] = t;)2 924 1 1392 3774 t
(for \(i = n; i > 1 && x[p=i/2] > x[i]; i = p\))13 3696 1 1392 3929 t
(swap\(p, i\);)1 924 1 1728 4084 t
(})1056 4239 w
(T extractmin\(\))1 1176 1 1056 4471 t
( i, c;)2 504({ int)1 588 2 1056 4626 t
(T t = x[1];)3 924 1 1392 4781 t
(x[1] = x[n--];)2 1176 1 1392 4936 t
(for \(i = 1; \(c = 2*i\) <= n; i = c\) {)12 3024 1 1392 5091 t
(if \(c+1 <= n && x[c+1] < x[c]\))7 2520 1 1728 5246 t
(c++;)2064 5401 w
(if \(x[i] <= x[c]\))3 1428 1 1728 5556 t
(break;)2064 5711 w
(swap\(c, i\);)1 924 1 1728 5866 t
(})1392 6021 w
(return t;)1 756 1 1392 6176 t
(})1056 6331 w
(};)720 6486 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-9)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 9 9
%%Page: 10 10
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
10 pagesetup
20 H f
(A Sort Using Heaps)3 1762 1 2179 960 t
(The Idea)1 794 1 720 1488 t
(Insert into a priority queue, then remove in order)8 4286 1 1008 1896 t
(The C++ Code)2 1314 1 720 2304 t
20 CW f
(template<class T>)1 2040 1 1296 2599 t
(void pqsort\(T v[], int n\))4 3000 1 1296 2834 t
( pq\(n\);)1 840({ priqueue<T>)1 1800 2 1296 3069 t
(int i;)1 720 1 1776 3304 t
(for \(i = 0; i < n; i++\))7 2760 1 1776 3539 t
(pq.insert\(v[i]\);)2256 3774 w
(for \(i = 0; i < n; i++\))7 2760 1 1776 4009 t
(v[i] = pq.extractmin\(\);)2 2760 1 2256 4244 t
(})1296 4479 w
20 H f
(Analysis)720 4947 w
20 HI f
(O)1008 5355 w
20 H f
(\()1180 5355 w
20 HI f
(n)1262 5355 w
20 H f
(log)1439 5355 w
20 HI f
(n)1772 5355 w
20 H f
(\) time)1 500 1 1900 5355 t
20 HI f
(n)1008 5763 w
20 H f
(items of extra space)3 1796 1 1176 5763 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-10)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 10 10
%%Page: 11 11
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
11 pagesetup
20 H f
(Heap Sort)1 904 1 2752 960 t
(The Idea)1 794 1 720 1488 t
(Use a heap with max on top.)6 2546 1 1008 1896 t
2340 2220 2340 4380 Dl
3780 2220 2340 2220 Dl
3780 4380 3780 2220 Dl
2340 4380 3780 4380 Dl
3780 3300 2340 2220 Dl
2340 4380 3780 3300 Dl
3780 3300 2340 3300 Dl
(heap)2476 2980 w
(heap)2476 3700 w
(?)3364 2620 w
(sorted)3141 4060 w
(Step 0)1 582 1 3892 2260 t
(Step)3892 3340 w
20 HI f
(n)4362 3340 w
20 H f
(Step 2)1 582 1 3892 4420 t
20 HI f
(n)4490 4420 w
20 S f
(-)4651 4420 w
20 H f
(1)4794 4420 w
(The Code)1 882 1 720 4944 t
20 CW f
(for i = [2, n])4 1680 1 1296 5239 t
(siftup\(i\))1776 5474 w
(for \(i = n; i >= 2; i--\))7 2880 1 1296 5709 t
(swap\(1, i\))1 1200 1 1776 5944 t
(siftdown\(i-1\))1776 6179 w
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-11)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 11 11
%%Page: 12 12
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
12 pagesetup
20 H f
(Heapsort Veri\256cation)1 1862 1 2129 960 t
20 CW f
(for i = [2, n])4 1680 1 720 1543 t
(/* heap\(1, i-1\) */)3 2160 1 1200 1778 t
(siftup\(i\))1200 2013 w
(/* heap\(1, i\) */)3 1920 1 1200 2248 t
(for \(i = n; i >= 2; i--\))7 2880 1 720 2718 t
( sorted\(i+1, n\))2 1800( &&)1 600(/* heap\(1, i\))2 1560 3 1200 2953 t
( x[i+1..n] */)2 1560( <=)1 600(&& x[1..i])1 1200 3 1800 3188 t
(swap\(1, i\))1 1200 1 1200 3423 t
(/* heap\(2, i-1\) && sorted\(i, n\))5 3720 1 1200 3658 t
( */)1 600(&& x[1..i-1] <= x[i..n])3 2760 2 1800 3893 t
(siftdown\(i-1\))1200 4128 w
(/* heap\(1, i-1\) && sorted\(i, n\))5 3720 1 1200 4363 t
( */)1 600(&& x[1..i-1] <= x[i..n])3 2760 2 1800 4598 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-12)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 12 12
%%Page: 13 13
%%PageBoundingBox: (atend)
DpostDict begin
/saveobj save def
mark
13 pagesetup
20 H f
(Principles)2626 960 w
(Ef\256ciency)720 1488 w
20 HI f
(shape)1008 1896 w
20 H f
(gives log time for)3 1516 1 1612 1896 t
20 HI f
(siftup)3184 1896 w
20 H f
(and)3720 1896 w
20 HI f
(siftdown)4112 1896 w
20 H f
(.)4848 1896 w
(Heapsort saves space by overlaying heap and)6 4120 1 1008 2304 t
(output.)1008 2544 w
(Correctness)720 2952 w
(Loop invariants.)1 1418 1 1008 3360 t
(Invariants of data structures \()4 2600 1 1008 3768 t
20 HI f
(shape)3608 3768 w
20 H f
(and)4212 3768 w
20 HI f
(order)4604 3768 w
20 H f
(\).)5072 3768 w
(Procedural Abstraction)1 2030 1 720 4176 t
(Abstract Data Types)2 1818 1 720 4584 t
6 H f
(From)720 7800 w
6 I f
(Programming Pearls)1 507 1 878 7800 t
6 R f
(, Copyright)1 274 1 1385 7800 t
6 S f
(\323)1674 7800 w
6 R f
( Pearls-14-13)1 3011(2000, Lucent Technologies)2 653 2 1736 7800 t
cleartomark
showpage
saveobj restore
end
%%PageBoundingBox: 61 -1 550 726
%%EndPage: 13 13
%%Trailer
DpostDict begin
done
end
%%Pages: 13
%%DocumentFonts: Courier Helvetica Times-Italic Times-Roman Symbol Helvetica-Oblique