Đang chuẩn bị liên kết để tải về tài liệu:
Lecture Data Structures: Lesson 31

Trúc Phương 137 16 ppt

Không đóng trình duyệt đến khi xuất hiện nút TẢI XUỐNG Tải xuống

Lecture Data Structures: Lesson 31 provide students with knowledge about buildheap; the general algorithm is to place the N keys in an array and consider it to be an unordered binary tree; the following algorithm will build a heap out of N keys; . | BuildHeap The general algorithm is to place the N keys in an array and consider it to be an unordered binary tree. The following algorithm will build a heap out of N keys. for i N 2 i gt 0 i- percolateDown i BuildHeap 1 Why I n 2 i 15 2 7 65 2 31 3 32 4 26 5 21 6 19 7 68 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 12 13 i 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 15 2 7 65 2 31 3 32 4 26 5 21 6 19 7 12 i 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 6 65 2 31 3 32 4 26 5 21 6 19 i 7 12 8 9 24 10 15 11 14 12 16 13 5 14 70 15 68 13 i 65 31 32 26 21 19 12 13 24 15 14 16 5 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 5 65 2 31 3 32 4 26 5 21 i 6 5 7 12 8 9 24 10 15 11 14 12 16 13 19 14 70 15 68 13 i 65 31 32 26 21 5 12 13 24 15 14 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 4 65 2 31 3 32 4 26 i 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 13 i 65 31 32 26 14 5 12 13 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 3 65 2 31 3 32 i 4 13 5 14 6 5 7 12 8 9 24 10 15 11 21 12 16 13 19 14 70 15 68 26 i 65 31 32 13 14 5 12 26 24 15 21 16 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i 2 65 2 31 i 3 5 4 13 5 14 6 16 7 12 8 9 24 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 31 5 13 14 16 12 26 24 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 i i 1 65 2 13 3 5 4 24 5 14 6 16 7 12 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 i 65 13 5 24 14 16 12 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 BuildHeap 1 Min heap 5 2 13 3 12 4 24 5 14 6 16 7 65 8 9 31 10 15 11 21 12 32 13 19 14 70 15 68 26 5 13 12 24 14 16 65 26 31 15 21 32 19 70 68 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Other Heap Operations decreaseKey p delta lowers the value of the key at position p by the amount delta . Since this might violate the heap order the