2008级计算机 内部资料,仅供课堂教学使用 DEFINITION: A heap is a list in which each entry contains a key, and, for all positions k in the list, the key at position k is at least as large as the keys in positions 2k and 2k+ 1, provided these positions exist in the list REMARK Many C++ manuals and textbooks refer to the area used for dynamic memory as the"heap", this use of the word"heap"has nothing to do with the present definition o Heapsort is suitable only for contiguous lists 8.9.2 Trace of heapsort P.364-367 Main function for heapsort P 365 Insertion into a heap: P 366 Building the initial heap: P. 368 8.9.3 Analysis of Heapsort P 368-369 In its worst case for sorting a list of length n, heapsort performs 2n Ig n o(n)comparisons of keys, and it performs n Ig n +o(n) assignments of entries 8.9.4 Priority DEFINITION: A priority queue consists of entries, such that each entry contains a key called the priority of the entry. A priority queue has only two operations other than the usual creation clearing, size, full, and empty operations Insert an entry. Remove the entry having the largest (or smallest) key If entries have equal keys, then any entry with the largest key may be removed first 18.10| Review: Comp arison of Methods P 372 Comparison of Sorting Methods P372-374 Use of space Use of computer time Programming effort Statistical analysis Empirical testing Pointers and Pitfalls 6 items F.375-376 Errata 324. UseS: line: Change "Record. The to "Record. the 331, "Uses: line of max key: Change "Record. The"to"Record, the p 334, Fig. 8.7: The arrow shafts are missing in the 3-Sorted"column. p. 362, E8(f): Insert a semicolon " "after "swap(i,j) p.371,E6. Change"lg(n+1)/(k+1))"to"lg(n/(k+1)"2008 级 计算机专业 数据结构 课堂教学笔记 内部资料，仅供课堂教学使用 DEFINITION: A heap is a list in which each entry contains a key, and, for all positions k in the list, the key at position k is at least as large as the keys in positions 2k and 2k + 1, provided these positions exist in the list. ⚫ REMARK Many C++ manuals and textbooks refer to the area used for dynamic memory as the “heap”; this use of the word “heap” has nothing to do with the present definition. ⚫ Heapsort is suitable only for contiguous lists. 8.9.2 Trace of heapsort P. 364-367 Main function for heapsort P. 365 Insertion into a heap: P. 366 Building the initial heap: P. 368 8.9.3 Analysis of Heapsort P. 368-369 In its worst case for sorting a list of length n, heapsort performs 2n lg n + O(n) comparisons of keys, and it performs n lg n + O (n) assignments of entries. 8.9.4 Priority Queues P. 369 DEFINITION: A priority queue consists of entries, such that each entry contains a key called the priority of the entry. A priority queue has only two operations other than the usual creation, clearing, size, full, and empty operations: Insert an entry. Remove the entry having the largest (or smallest) key. If entries have equal keys, then any entry with the largest key may be removed first. [8.10] Review: Comparison of Methods P.372 Comparison of Sorting Methods P.372-374 ⚫ Use of space ⚫ Use of computer time ⚫ Programming effort ⚫ Statistical analysis ⚫ Empirical testing Pointers and Pitfalls 6 items P.375-376 ------------------------------------------------------------------------------------------------------------------------------- Errata p. 324, "Uses:" line: Change "Record. The" to "Record, the". p. 331, "Uses:" line of max_key: Change "Record. The" to "Record, the". p. 334, Fig. 8.7: The arrow shafts are missing in the "3-Sorted" column. p. 362, E8(f): Insert a semicolon ";" after "swap(i,j)". p. 371, E6: Change "lg((n+1)/(k+1))" to "lg(n/(k+1))". -------------------------------------------------------------------------------------------------------------------------------