intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Sắp xếp vun đống

Chia sẻ: Đinh Miên | Ngày: | Loại File: PPT | Số trang:67

Thêm vào BST
Báo xấu
151
lượt xem 24
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Sắp xếp vun đống - Heap sort • Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sắp xếp vun đống

  1. Sắp xếp vun đống Heap sort
  2. Sắp xếp vun đống - Heap sort • Khi tìm phần tử nhỏ nhất ở bước i, phương pháp sắp xếp chọn trực tiếp không tận dụng được các thông tin đã có được do các phép so sánh ở bước i-1. Vì lý do trên người ta tìm cách xây dựng một thuật toán sắp xếp có thể khắc phục nhược điểm này. • Mấu chôt để giải quyết vấn đề vừa nêu là phải tìm ra được một cấu trúc dữ liệu cho phép tích lũy các thông tin về sự so sánh giá trị các phần tử trong qua trình sắp xếp. • Giả sử dữ liệu cần sắp xếp được bố trí theo quan hệ so sánh và tạo thành sơ đồ dạng cây như sau :
  3. heap Các phần tử tốt nhất (xấu nhất) sẽ được dời lên trên
  4. Cấu trúc heap • Heap là một cấu trúc dữ liệu dạng hình cây có tính chất sau: • Mổi một phần tử sẽ có nhiều nhất 2 phần tử là con của nó (phần tử liên đới) • Bất kỳ Phần tử ở trên (cha) sẽ có giá trị lớn hơn giá trị 2 phần tử con của nó • Phần tử đầu (phần tử gốc) sẽ là phần tử có giá trị lớn nhất trong heap
  5. Cấu trúc heap gốc 16 cha 12 14 Con Con 11 4 9 13 (phần tử liên đới) (phần tử liên đới) 7 6 2 1 0 8 3 10 5 16 l giá 12 n nh 12 >à11, trị lớ> 4 ất trong heap
  6. • Heap có các tính chất sau : • Tính chất 1 : Nếu al , al+1 ,al+2... , ar là một heap thì khi cắt bỏ một số phần tử ở hai đầu của heap, dãy con còn lại vẫn là một heap. • Tính chất 2 : Nếu a1 , a2 ,... , an là một heap thì phần tử a1 (đầu heap) luôn là phần tử lớn nhất trong heap. • Tính chất 3 : Mọi dãy al , al+1 ,al+2... , ar với 2l > r là một heap.
  7. Cấu trúc heap • Cài đặt cấu trúc heap bằng mảng a0,   a1 ,... , ar thoả các quan hệ sau với mọi i ‫ﻴ‬ 0], r]: - ai > = a2i+1 - ai >= a2i+2 (a2i+1, a2i+2) là các cặp phần tử liên đới • phần tử a0 (đầu heap) luôn là phần tử lớn nhất trong heap. • Vậy ak có phần tử liên đới là a2k+1, a2k+2
  8. gốc 16 cha 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 a0= 16  gốc a1=12 có 2 phần tử liên đới là a 2x1+1=a3 =11 a2x1+2=a4=4
  9. Cấu trúc heap • Vấn đề cần quan tâm – Làm sao xây dựng heap – Thêm 1 phần tử – Xóa 1 phần tử  phải đảm bảo tính chất heap
  10. Cấu trúc heap • Thêm 1 phần tử – Thêm vào cuối mảng  mất tính chất heap Cập nhật lại heap (upheap) Bước 1:tại k kiểm tra so với cha của nó (k1-1)/2 Nếu ak a(k-1)/2 đổi vị trí  bước 1
  11. Cấu trúc heap 16 • Thêm 15 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
  12. Cấu trúc heap 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 15 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  13. Cấu trúc heap 16 12 14 11 4 9 13 15 6 2 1 0 8 3 10 5 7 16 12 14 11 4 9 13 15 6 2 1 0 8 3 10 5 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  14. Cấu trúc heap 16 12 14 15 4 9 13 11 6 2 1 0 8 3 10 5 7 16 12 14 15 4 9 13 11 6 2 1 0 8 3 10 5 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  15. Cấu trúc heap 16 15 14 12 4 9 13 11 6 2 1 0 8 3 10 5 7 16 15 14 12 4 9 13 11 6 2 1 0 8 3 10 5 7 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
  16. Cấu trúc heap (C) • Thuật toán upheap • Void uphead(int a[], int N){ • Int k=N-1; • While (k>0)&&(a[k]>a[(k)/2]) {hoanvi(a[k],a[k/2]);k=k/2;} • }
  17. Cấu trúc heap (C#) • Thuật toán upheap • Void uphead(){ • Int k=N-1; • While (k>0)&&(a[k]>a[(k-1)/2]) { • hoanvi(ref a[k],ref a[(k-1)/2]); • k=(k-1)/2; • } • }
  18. Cấu trúc heap • Xóa phần tử • Thông thường cấu trúc heap thường lấy phần tử gốc (đầu) ra khỏi heap  mất tính chất heap cập nhật heap
  19. Cấu trúc heap • Cách giải quyết 1: • Chọn trong 2 phần tử liên đới phần tử nào lớn hơn thì đưa lên  mảng bị phân mảnh, trống
  20. Cấu trúc heap • Lấy gốc ra 16 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 16 12 14 11 4 9 13 7 6 2 1 0 8 3 10 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2