Lớp 2 - liên kết tri thức
Lớp 2 - Chân trời sáng tạo
Lớp 2 - Cánh diều
Tài liệu tham khảo
Lớp 3Sách giáo khoa
Tài liệu tham khảo
Sách VNEN
Lớp 4Sách giáo khoa
Sách/Vở bài xích tập
Đề thi
Lớp 5Sách giáo khoa
Sách/Vở bài tập
Đề thi
Lớp 6Lớp 6 - liên kết tri thức
Lớp 6 - Chân trời sáng tạo
Lớp 6 - Cánh diều
Sách/Vở bài tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 7Sách giáo khoa
Sách/Vở bài bác tập
Đề thi
Chuyên đề & Trắc nghiệm
Lớp 8Sách giáo khoa
Sách/Vở bài xích tập
Đề thi
Chuyên đề và Trắc nghiệm
Lớp 9Sách giáo khoa
Sách/Vở bài bác tập
Đề thi
Chuyên đề và Trắc nghiệm
Lớp 10Sách giáo khoa
Sách/Vở bài xích tập
Đề thi
Chuyên đề và Trắc nghiệm
Lớp 11Sách giáo khoa
Sách/Vở bài xích tập
Đề thi
Chuyên đề và Trắc nghiệm
Lớp 12Sách giáo khoa
Sách/Vở bài xích tập
Đề thi
Chuyên đề & Trắc nghiệm
ITNgữ pháp giờ Anh
Lập trình Java
Phát triển web
Lập trình C, C++, Python
Cơ sở dữ liệu
Cấu trúc dữ liệu và giải thuậtMột số khái niệm về Giải thuật cấu trúc dữ liệu mảng (Array)Danh sách links - Linked ListsNgăn xếp và Hàng đợiMột số giải thuật tìm kiếmMột số lời giải sắp xếpCấu trúc tài liệu đồ thị (Graph)Cấu trúc dữ liệu câyĐệ qui (Recursion)Tài liệu xem thêm
Cấu trúc tài liệu Heap
Trang trước
Trang sau
Cấu trúc tài liệu Heap là gì ?
Cấu trúc dữ liệu Heap là một trong trường hợp quan trọng của kết cấu dữ liệu cây nhị phân cân bằng, trong các số đó khóa của nút cội được đối chiếu với những con của nó và được thu xếp một giải pháp phù hợp. Trường hợp α tất cả nút bé β thì:
key(α) ≥ key(β)
Khi cực hiếm của nút phụ vương lớn hơn quý giá của nút con, thì trực thuộc tính này tạo thành một Max Heap. Dựa trên tiêu chuẩn này, một Heap rất có thể là một trong hai dạng hình sau:
Với dữ liệu đầy vào → 35 33 42 10 14 19 27 44 26 31Min-Heap: tại chỗ này giá trị của nút cội là nhỏ dại hơn hoặc bằng các giá trị của những nút con.
Bạn đang xem: Heap là gì
Max-Heap: tại đây giá trị của nút gốc là to hơn hoặc bằng giá trị của các nút con.
Hai cây lấy một ví dụ trên hầu hết được xây dựng dựa trên cùng một tài liệu đầu vào và thuộc thứ tự.
Giải thuật xây đắp Max Heap
Chúng ta sẽ áp dụng cùng ví dụ trên để minh họa cách tạo một Max Heap. Phương thức để thi công Min Heap là tương tự.
Chúng ta đang suy ra một giải thuật cho Max Heap bằng việc chèn 1 phần tử tại một thời điểm. Tại bất cứ thời điểm nào, Heap đa số phải duy trì (tuân theo) ở trong tính của nó. Trong quá trình chèn, bọn họ cũng trả sử rằng bọn họ đang chèn một nút vào trong HEAPIFIED Tree.
Bước 1: chế tạo một nút new tại vị trí sau cùng của Heap.Bước 2: Gán giá trị mới cho nút này.Bước 3: so sánh giá trị của nút con với giá trị cha.Bước 4: Nếu cực hiếm của phụ thân là bé dại hơn nhỏ thì tráo thay đổi chúng.Bước 5: tái diễn bước 3 với 4 cho tới khi vẫn duy trì thuộc tính của Heap.
Ghi chú: Trong giải mã xây dựng Min Heap, cực hiếm của nút cha sẽ là nhỏ dại hơn giá chỉ trị của các nút con.
Để rõ rộng về lời giải xây dựng Max Heap, bọn họ hãy quan sát vào hình minh họa cồn dưới đây.
Giải thuật xóa vào Max Heap
Hoạt hễ xóa vào Max (hoặc Min) Heap luôn luôn ra mắt tại nút gốc và nhằm xóa giá trị lớn nhất (hoặc bé dại nhất). Các bạn theo dõi giải mã và hình minh họa động dưới đây để gọi thêm về giải mã này.
Bước 1: Xóa nút gốc.Bước 2: Di chuyển bộ phận cuối cùng tất cả bậc thấp tuyệt nhất lên nút gốc.Bước 3: đối chiếu giá trị của nút nhỏ này với mức giá trị của cha.Bước 4: Nếu quý giá của phụ thân là nhỏ dại hơn của con thì tráo đổi chúng.Bước 5: tái diễn bước 3 và 4 cho tới khi vẫn duy trì thuộc tính của Heap.
Đã có app movingthenationforward.com trên năng lượng điện thoại, giải bài bác tập SGK, SBT soạn văn, Văn mẫu, Thi online, bài giảng....miễn phí. Cài đặt ngay vận dụng trên android và iOS.
Xem thêm: Giải Bài 31 Trang 19 Sgk Toán 6 Tập 2, 33 Trang 19 Sgk Toán 6 Tập 2
Follow fanpage facebook của team https://www.facebook.com/movingthenationforward.comteam/ hoặc facebook cá nhân Nguyễn Thanh Tuyền https://www.facebook.com/tuyen.movingthenationforward.com để tiếp tục theo dõi các loạt bài mới nhất về Java,C,C++,Javascript,HTML,Python,Database,Mobile.... Tiên tiến nhất của bọn chúng tôi.