Lecture Data Structures: Lesson 29

Lecture Data Structures: Lesson 29 provide students with knowledge about complete binary tree; the heap ADT; the parent node has key smaller than or equal to both of its children nodes; heap property violated; inserting into a heap; . | Data Structures Lecture 29 Sohail Aslam 1 Complete Binary Tree 1 A 2 3 B C 4 5 6 7 D E F G 8 9 10 H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Question why don t we store all binary trees in arrays Why use pointers 2 The Heap ADT 3 Heap A heap is a complete binary tree that conforms to the heap order. The heap order property in a min heap for every node X the key in the parent is smaller than or equal to the key in X. Or the parent node has key smaller than or equal to both of its children nodes. 4 Heap 13 21 16 24 31 19 68 65 26 32 This is a min heap 5 Heap Not a heap heap property violated 13 21 19 6 31 16 68 65 26 32 6 Heap Analogously we can define a max-heap where the parent has a key larger than the its two children. Thus the largest key would be in the root. 7 Inserting into a Heap 1 13 2 21 3 16 4 24 5 31 6 19 7 68 8 9 26 10 32 65 This is an existing heap 13 21 16 24 31 19 68 65 26 32 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 8 Inserting into a Heap 1 insert 14 13 2 21 3 16 4 24 5 31 6 19 7 68 8 9 26 10 32 11 14 65 13 21 16 24 31 19 68 65 26 32 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 9 Inserting into a Heap 1 insert 14 13 2 21 3 16 4 24 5 31 6 19 7 68 8 9 26 10 32 11 65 13 21 16 24 31 19 68 65 26 32 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 10 Inserting into a Heap 1 insert 14 13 2 21 3 16 4 24 5 6 19 7 68 8 9 26 10 32 11 31 65 13 21 16 24 19 68 65 26 32 31 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 11 Inserting into a Heap 1 insert 14 13 2 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 65 13 16 24 21 19 68 65 26 32 31 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 12 Inserting into a Heap 1 insert 14 13 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 65 13 14 16 24 21 19 68 65 26 32 31 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13 Inserting into a Heap 1 insert 14 with 13 exchange 2 21 3 16 4 24 5 31 6 19 7 68 8 9 26 10 32 11 14 65 13 21 16 24 31 19 68 65 26 32 14 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 14 Inserting into a Heap 1 insert 14 with 13 exchange 2 21 3 16 4 24 5 14 6 19 7 68 8 9

Không thể tạo bản xem trước, hãy bấm tải xuống
TÀI LIỆU MỚI ĐĂNG
9    76    2    29-03-2024
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.