Heap Sort Là Gì

Sắp xếp vun lô (Heap Sort) là 1 trong chuyên môn sắp xếp phân nhiều loại dựa vào một kết cấu tài liệu được Điện thoại tư vấn là đụn nhị phân (binary heap), Call dễ dàng là gò. Nó tương tự nlỗi thuật toán thù Sắp xếp lựa chọn (Selection Sort) vị trí phần tử lớn nhất sẽ tiến hành xếp vào cuối danh sách. Lặp đi lặp lại công việc này cho các phần tử còn sót lại của list.

Bạn đang xem: Heap sort là gì

Phân loại: Thuật toán thù sắp xếpCấu trúc dữ liệu: MảngHiệu suất trường đúng theo xấu nhất: O(nlogn)Hiệu suất trường hợp tốt nhất: O (nlogn) (các khóa riêng biệt) hoặc O(n) (những khóa bởi nhau)Hiệu suất trung bình: O(nlogn)Trường thích hợp tinh vi tốt nhất về không gian: O(1)

Khái niệm lô nhị phân (binary heap)

Mỗi mảng a<1..n> có thể coi nlỗi một cây nhị phân gần đầy (có trọng số là những quý giá của mảng), với gốc sinh sống thành phần trước tiên, con bên trái của đỉnh aa<2*i> bé mặt buộc phải là a<2*i+1> (nếu mảng ban đầu từ 1 còn giả dụ mảng bước đầu trường đoản cú 0 thì nhì nhánh bé là a<2*i+1> a<2*i+2>) (trường hợp 2*i ≤ n hoặc 2*i+1 ≤ n, lúc ấy những phần tử gồm chỉ số to hơn (int) (n/2) không có nhỏ, vì vậy là lá).

Một cây nhị phân, được Hotline là lô cực to trường hợp khóa của đa số nút không nhỏ rộng khóa các bé của nó. Lúc biểu diễn một mảng a< > vày một cây nhi phân theo máy từ bỏ thoải mái và tự nhiên điều đó tức là a ≥ a<2*i> với a ≥ a<2*i+1> cùng với mọi i =1..int(n/2). Ta cũng biến thành Điện thoại tư vấn mảng những điều đó là đụn. do vậy vào gò a<1> (ứng với cội của cây) là bộ phận lớn nhất. Mảng bất kỳ chỉ bao gồm một phần tử luôn luôn vẫn là một gò.Một lô rất tè được tư tưởng theo những bất đẳng thức ngược lại: a ≤ a<2*i> cùng a ≤ a<2*i+1>. Phần tử đứng sống cội cây cực tiểu là thành phần nhỏ tuổi độc nhất.Kỹ thuật vun đống

Việc thu xếp lại những phần tử của một mảng ban đầu làm thế nào để cho nó đổi thay gò được hotline là vun lô.

Vun đống trên đỉnh máy i

Nếu nhị cây bé cội 2*i2*i+1 vẫn là đụn thì để cây nhỏ gốc i đổi thay đống chỉ bài toán so sánh cực hiếm a với mức giá trị to hơn trong nhị quý giá a<2*i> cùng a<2*i+1>, nếu a nhỏ dại hơn nữa thì thay đổi vị trí chúng lẫn nhau. Nếu thay đổi vị trí mang đến a<2*i>, liên tiếp đối chiếu cùng với con lớn hơn trong nhị nhỏ của chính nó cho đên lúc hoặc chạm chán đỉnh lá.

Vun một mảng thành đống

Để vun mảng a<1..n> thành đống ta vun tự bên dưới lên, ban đầu trường đoản cú bộ phận a với j = Int (n/2) ngược lên tới a<1>.

Sắp xếp bằng vun đốngĐổi chỗ (Swap): Sau Khi mảng a<1..n> đang là đụn, rước phần tử a<1> bên trên đỉnh của đụn thoát khỏi đống đặt vào vị trí cuối cùng n, cùng đưa thành phần trang bị ở đầu cuối a Tột Đỉnh gò thì thành phần a đã có đứng đúng vị trí.

Xem thêm: Hướng Dẫn Cách Chỉnh Dàn Karaoke Để Âm Thanh Hay Nhất, Chỉnh Âm Thanh Loa Kéo Karaoke Để Hát Chuẩn Nhất

Vun lại: Phần còn sót lại của mảng a<1..n-1> chỉ không giống cấu trúc gò sinh hoạt phần tử a<1>. Vun lại mảng này thành lô với n-một trong những phần tử.Lặp: Tiếp tục với mảng a<1..n-1>. Quá trình dừng lại khi đống chỉ còn lại một trong những phần tử.Ví dụ

lấy ví dụ như 01: Cho mảng a=(2,3,5,6,4,1,7), Tại trên đây n = 7. Các thành phần từ a<4> cho a<7> là lá.

Tạo đống

Vun cây gốc a<3> ta được mảng a=(2,3,7,6,4,1,5)Vun cây cội a<2> ta được mảng a=(2,6,7,3,4,1,5)Vun cây nơi bắt đầu a<1> ta được mảng a=(7,6,5,3,4,1,2)

Bây giờ đồng hồ a=(7,6,5,3,4,1,2) sẽ là đụn.

Sắp xếp vun đống


Đổi vị trí a<1> với a<7>: a=(2,6,5,3,4,1,7) với vun lại mảng a<1..6> ta được mảng a=(6,4,5,3,2,1,7)Đổi nơi a<1> với a<6>: a=(1,4,5,3,2,6,7) cùng vun lại mảng a<1..5> ta được mảng a=(5,4,1,3,2,6,7)Đổi chỗ a<1> với a<5>: a=(1,4,2,3,5,6,7) và vun lại mảng a<1..4> ta được mảng a=(4,3,1,2,5,6,7)Đổi địa điểm a<1> cùng với a<4>: a=(1,3,2,4,5,6,7) cùng vun lại mảng a<1..3> ta được mảng a=(3,2,1,4,5,6,7)Đổi nơi a<1> cùng với a<3>: a=(2,1,3,4,5,6,7) cùng vun lại mảng a<1..2> ta được mảng a=(2,1,3,4,5,6,7)Đổi nơi a<1> cùng với a<2>:a=(1,2,3,4,5,6,7) Mảng còn sót lại chỉ một phần tử.Quá trình sắp xếp đã chấm dứt.

Ví dụ 02: Sắp xếp mảng  6, 5, 3, 1, 8, 7, 2, 4 từ bỏ nhỏ dại mang lại phệ thực hiện cách thức vun đống

Tạo đống

ĐốngPhần tử mới nhận thêm vàoĐổi địa điểm phần tử
null6
65
6, 53
6, 5, 31
6, 5, 3, 18
6, 5, 3, 1, 85, 8
68, 3, 1, 56, 8
8, 6, 3, 1, 57
8, 6, 3, 1, 5, 73, 7
8, 6, 7, 1, 5, 32
8, 6, 7, 1, 5, 3, 24
8, 6, 7, 1, 5, 3, 2, 41, 4
8, 6, 7, 4, 5, 3, 2, 1

Sắp xếp (vun đống)

HeapPhần tử hân oán đổiXóa phần tửmảng sắp đến xếpbỏ ra tiết
8 , 6, 7, 4, 5, 3, 2, 18, 1hoán thù thay đổi 8 với 1 nhằm xóa 8 tự đống
1, 6, 7, 4, 5, 3, 2, 8số 8xóa 8 từ heap cùng tiếp tế mảng đã chuẩn bị xếp
1 , 6, 7 , 4, 5, 3, 21, 7số 8hoán thù thay đổi 1 và 7 vì chưng bọn chúng không áp theo đồ vật từ vào đống
7, 6, 1 , 4, 5, 3 , 21, 3số 8hoán thù thay đổi 1 với 3 do chúng không áp theo sản phẩm công nghệ từ vào đống
7 , 6, 3, 4, 5, 1, 27, 2số 8hoán thù đổi 7 và 2 để xóa 7 từ đống
2, 6, 3, 4, 5, 1, 77số 8xóa 7 trường đoản cú heap cùng chế tạo mảng đang chuẩn bị xếp
2 , 6 , 3, 4, 5, 12, 67, 8hoán đổi 2 và 6 do bọn chúng không tuân theo vật dụng từ bỏ trong đống
6, 2 , 3, 4, 5 , 12, 57, 8hoán thay đổi 2 cùng 5 vày chúng không tuân theo vật dụng trường đoản cú trong đống
6 , 5, 3, 4, 2, 16, 17, 8hân oán thay đổi 6 cùng 1 nhằm xóa 6 tự đống
1, 5, 3, 4, 2, 667, 8xóa 6 từ bỏ heap và cấp dưỡng mảng vẫn sắp tới xếp
1 , 5 , 3, 4, 21, 56, 7, 8hoán thay đổi 1 và 5 do bọn chúng không tuân theo trang bị trường đoản cú trong đống
5, 1 , 3, 4 , 21, 46, 7, 8hoán thù thay đổi 1 cùng 4 bởi vì chúng không áp theo máy từ trong đống
5 , 4, 3, 1, 25, 26, 7, 8hân oán đổi 5 và 2 nhằm xóa 5 trường đoản cú đống
2, 4, 3, 1, 556, 7, 8xóa 5 trường đoản cú heap và thêm vào mảng đang chuẩn bị xếp
2 , 4 , 3, 12, 45, 6, 7, 8hoán đổi 2 và 4 bởi vì bọn chúng không áp theo thiết bị trường đoản cú trong đống
4 , 2, 3, 14, 15, 6, 7, 8hoán thay đổi 4 với 1 để xóa 4 từ bỏ đống
1, 2, 3, 445, 6, 7, 8xóa 4 trường đoản cú heap cùng cung ứng mảng đang sắp đến xếp
1 , 2, 31, 34, 5, 6, 7, 8hoán đổi 1 cùng 3 bởi chúng không áp theo vật dụng trường đoản cú vào đống
3 , 2, 13, 14, 5, 6, 7, 8hoán đổi 3 với 1 để xóa 3 trường đoản cú đống
1, 2, 334, 5, 6, 7, 8xóa 3 tự heap và chế tạo mảng đang sắp đến xếp
1 , 21, 23, 4, 5, 6, 7, 8hoán thù thay đổi 1 và 2 vì chúng không tuân theo thiết bị từ trong đống
2 , 12, 13, 4, 5, 6, 7, 8hoán thù đổi 2 với 1 nhằm xóa 2 từ bỏ đống
1, 223, 4, 5, 6, 7, 8xóa 2 tự heap và cấp dưỡng mảng đã sắp tới xếp
112, 3, 4, 5, 6, 7, 8xóa 1 từ heap và tiếp tế mảng đang sắp tới xếp
1, 2, 3, 4, 5, 6, 7, 8trả thành
*
Hình ảnh minch hoạ mang lại lấy một ví dụ 02 thuật toán sắp xếp vun đốngSắp xếp vun đống trong xây dựng C++

Sắp xếp một mảng arr<> = 12, 11, 13, 5, 6, 7 theo máy trường đoản cú tăng mạnh thực hiện phương thức vun đụn bằng ngôn từ thiết kế C++. Nhấp đôi vào code nhằm copy với chạy thử coi kết quả.

#include using namespace std;// Vun dong mot cay bé teo nut root la i// n la kich thuoc cua dongvoid heapify(int arr<>, int n, int i)int largest = i; // khoi tao largest nhu la rootint l = 2 * i + 1; // left = 2*i + 1int r = 2 * i + 2; // right = 2*i + 2// Neu nut đàn ông lon hon so voi rootif (l arr)largest = l;// Neu nut con pnhị lon hon so voi rootif (r arr)largest = r;// Neu root khong pnhị la lon nhatif (largest != i)swap(arr, arr);// De quy lai đê mê heapifyheapify(arr, n, largest);// Ham vun dongvoid heapSort(int arr<>, int n)// Tao mot dong (Sap xep lai mang)for (int i = n / 2 - 1; i >= 0; i--)heapify(arr, n, i);// Trích xuất từng một trong những phần tử một trường đoản cú heapfor (int i = n - 1; i >= 0; i--)// Di chuyen root ve sầu cuoi cungswap(arr<0>, arr);// goi đắm đuối heapifyheapify(arr, i, 0);void printArray(int arr<>, int n){for (int i = 0; i