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

Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ

Lecture Data Structures: Lesson 30 provide students with knowledge about inserting into a Heap; finding the minimum is easy; it is at the top of the heap; deleting it (or removing it) causes a hole which needs to be filled; . | Data Structures Lecture 30 Sohail Aslam 1 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 12 15 65 13 14 16 24 21 19 68 65 26 32 31 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 2 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 16 4 24 5 21 6 15 7 68 8 9 26 10 32 11 31 12 19 65 13 14 16 24 21 15 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 3 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 4 Inserting into a Heap 1 insert 15 with 13 exchange 2 14 3 15 4 24 5 21 6 16 7 68 8 9 26 10 32 11 31 12 19 65 13 14 15 24 21 16 68 65 26 32 31 19 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 5 DeleteMin Finding the minimum is easy it is at the top of the heap. Deleting it or removing it causes a hole which needs to be filled. 1 13 2 14 3 16 4 24 5 21 6 19 7 68 8 9 26 10 32 11 31 65 6 DeleteMin deleteMin 1 2 14 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 7 DeleteMin deleteMin 1 14 2 3 16 4 24 5 6 19 7 68 21 8 9 26 10 32 11 31 65 8 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 8 9 26 10 32 11 31 65 9 DeleteMin deleteMin 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 11 65 10 DeleteMin deleteMin heap size is reduced by 1. 1 14 2 21 3 16 4 24 5 6 19 7 68 31 8 9 26 10 32 65 11 BuildHeap Suppose we are given as input N keys or items and we want to build a heap of the keys. Obviously this can be done with N successive inserts. Each call to insert will either take unit time leaf node or log2N if new key percolates all the way up to the root . 12 BuildHeap The worst time for building a heap of N keys could be Nlog2N. It turns out that we can build a heap in linear time. 13 BuildHeap Suppose we have a method percolateDown p which moves down the key in node p downwards. This is what was happening in deleteMin. 14 BuildHeap Initial data N 15 65 31 32 26 21 19 68 13 24 15 14 16 5 70 12 0 1 2 3 4 5 6 7

TAILIEUCHUNG - Chia sẻ tài liệu không giới hạn
Địa chỉ : 444 Hoang Hoa Tham, Hanoi, Viet Nam
Website : tailieuchung.com
Email : tailieuchung20@gmail.com
Tailieuchung.com là thư viện tài liệu trực tuyến, nơi chia sẽ trao đổi hàng triệu tài liệu như luận văn đồ án, sách, giáo trình, đề thi.
Chúng tôi không chịu trách nhiệm liên quan đến các vấn đề bản quyền nội dung tài liệu được thành viên tự nguyện đăng tải lên, nếu phát hiện thấy tài liệu xấu hoặc tài liệu có bản quyền xin hãy email cho chúng tôi.
Đã 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.