Sắp xếp vun đống

Mô phỏng thuật toán sắp xếp vun đống

Sắp xếp vun đống (Heapsort) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp.

Đống (Heap)

[sửa | sửa mã nguồn]
  • Ví dụ về mảng và cây nhị phân tương ứng
    Mỗi mảng a[1..n] có thể xem như một cây nhị phân gần đầy (có trọng số là các giá trị của mảng), với gốc ở phần tử thứ nhất, con bên trái của đỉnh a[i] là a[2*i] con bên phải là a[2*i+1] (nếu mảng bắt đầu từ 1 còn nếu mảng bắt đầu từ 0 thì hai con là a[2*i+1] và a[2*i+2]) (nếu 2*i<=n hoặc 2*i+1<=n, khi đó các phần tử có chỉ số lớn hơn không có con, do đó là ) (leaf).
  • Ví dụ mảng (45,23,35,13,15,12,15,7,9) là một đống
    • Một cây nhị phân, được gọi là đống cực đại nếu khóa của mọi nút không nhỏ hơn khóa các con của nó. Khi biểu diễn một mảng a[] bởi một cây nhi phân theo thứ tự tự nhiên điều đó nghĩa là a[i]>=a[2*i] và a[i]>=a[2*i+1] với mọi i =1..int(n/2). Ta cũng sẽ gọi mảng như vậy là đống. Như vậy trong đống a[1] (ứng với gốc của cây) là phần tử lớn nhất. Mảng bất kỳ chỉ có một phần tử luôn luôn là một đống.
    • Một đống cực tiểu được định nghĩa theo các bất đẳng thức ngược lại: a[i]<=a[2*i] và a[i]<=a[2*i+1]. Phần tử đứng ở gốc cây cực tiểu là phần tử nhỏ nhất.

Vun đống

[sửa | sửa mã nguồn]

Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.

Vun đống tại đỉnh thứ i

[sửa | sửa mã nguồn]

Nếu hai cây con gốc đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị với giá trị lớn hơn trong hai giá trị , nếu nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho , tiếp tục so sánh với con lớn hơn trong hai con của nó cho đên khi hoặc gặp đỉnh lá. (Thủ tục DownHeap trong giả mã dưới đây)

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

[sửa | sửa mã nguồn]

Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j]với j =Int(n/2) ngược lên tới a[1]. (Thủ tục MakeHeap trong giả mã dưới đây)

Sắp xếp bằng vun đống

[sửa | sửa mã nguồn]
Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.
Vun lại: Phần còn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 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 phần tử.

Cho mảng a=(2,5,8,12,45,13,45,78)

Ở đây n = 7. Các phần tử từ a[4] đến a[7] là lá.

Vun đống

[sửa | sửa mã nguồn]
  • Vun cây gốc a[3] ta được mảng a=(2,3,7,6,4,1,5)
  • Vun cây gốc a[2] ta được mảng a=(2,6,7,3,4,1,5)
  • Vun cây gốc a[1] ta được mảng a=(7,6,5,3,4,1,2)
  • Bây giờ a=(7,6,5,3,4,1,2) đã là đống.

Sắp xếp

[sửa | sửa mã nguồn]
  • Đổi chỗ a[1] với a[7]: a=(2,6,5,3,4,1,7)
    và vun lại mảng a[1..6] ta được mảng a=(6,4,5,3,2,1,7)
  • Đổi chỗ a[1] với a[6]: a=(1,4,5,3,2,6,7)
    và 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=(2,4,1,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 chỗ a[1] với a[4]: a=(2,3,1,4,5,6,7)
    và vun lại mảng a[1..3] ta được mảng a=(3,2,1,4,5,6,7)
  • Đổi chỗ a[1] với a[3]: a=(1,2,3,4,5,6,7)
    và vun lại mảng a[1..2] ta được mảng a=(2,1,3,4,5,6,7)
  • Đổi chỗ a[1] với a[2]:a=(1,2,3,4,5,6,7)
  • Mảng còn lại chỉ một phần tử. Quá trình sắp xếp đã xong.

Mã giả bằng ngôn ngữ C có sử dụng câu trúc dữ liệu

[sửa | sửa mã nguồn]
#include <stdio.h>
#include <conio.h>

const int n = 10;
typedef int keytype;
typedef float othertype;
typedef struct recordtype {
    keytype key;
    othertype otherfields;
};
// khai bao mang a co n phan tu
recordtype a[n];

void Swap(recordtype &x, recordtype &y)
{
    recordtype temp;
    temp = x;
    x = y;
    y = temp;
}

void PushDown(int first, int last)
{
    //while (r <= (last - 1) / 2)
    if (first == last || first > (last - 1) / 2) return;
    if (last == 2 * first + 1) {
        if (a[first].key > a[last].key)
            Swap(a[first], a[last]);
        //first = last;
        return;
    } else if ((a[first].key > a[2*first+1].key) && (a[2*first+1].key <= a[2*first+2].key))
    {
        Swap(a[first], a[2*first+1]);
        PushDown(2 * first + 1, last);
    } else if ((a[first].key > a[2*first+2].key) && (a[2*first+2].key < a[2*first+1].key))
    {
        Swap(a[first], a[2*first+2]);
        PushDown(2 * first + 2, last);
    }
    else return; //first = last;
}

void HeapSort(void)
{   int i;
    for(i = (n-2) / 2; i >= 0; i--)
        PushDown(i, n-1);
    for(i = n-1; i>=2; i--) {
        Swap(a[0], a[i]);
        PushDown(0, i-1);
    }
    Swap(a[0], a[1]);
}

void readList(recordtype a[])
{
    for (int i = 0; i < n; i++)
    {
        printf("Phan tu %d = ", i+1);
        scanf("%d",&a[i]);
    }
}
void printList(recordtype a[])
{
    for (int i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
}
int main()
{
    printf("Nhap %d phan tu cho danh sach.\n", n);
    readList(a);
    printf("Danh sach sau khi duoc nhap: \n");
    printList(a);
    HeapSort();
    printf("\nDanh sach sau khi duoc sap xep: \n");
    printList(a);
    getch();
    return 0;
}

Ứng dụng

[sửa | sửa mã nguồn]
  • Ngoài giải thuật sắp xếp vun đống, cấu trúc đống còn được ứng dụng trong nhiều giải thuật khác, khi cần lấy ra nhanh chóng các phần tử lớn nhất (hoặc nhỏ nhất) của một dãy phần tử, chẳng hạn trong hàng đợi có ưu tiên trong đó tiêu chuẩn ưu tiên là có khóa lớn nhất (hoặc nhỏ nhất). Có thể tìm thấy điều đó trong giải thuật tìm bộ mã Huffman cho một bảng tần số của các ký tự.(tacgia)

Tham khảo

[sửa | sửa mã nguồn]
Chúng tôi bán
Bài viết liên quan
Nguồn gốc Mặt Nạ Kháng Ma trong Tensura
Nguồn gốc Mặt Nạ Kháng Ma trong Tensura
Ngay từ khi bắt đầu Tensura, hẳn chúng ta đã quá quen thuộc với hình ảnh Shizu và chiếc mặt nạ, thứ mà sau này được cô để lại cho Rimuru
Borrowed Time - bộ phim ngắn khá u tối của Pixar
Borrowed Time - bộ phim ngắn khá u tối của Pixar
Pixar Animation Studios vốn nổi tiếng với những bộ phim hơi có phần "so deep"
10 địa điểm du lịch đáng đi tại Việt Nam trong dịp Tết
10 địa điểm du lịch đáng đi tại Việt Nam trong dịp Tết
Tết là thời điểm chúng ta nghỉ ngơi sau một năm làm việc căng thẳng. Ngoài việc về quê thăm hỏi họ hàng thì thời gian còn lại mọi người sẽ chọn một điểm để du lịch cùng gia đình. Nếu bạn không muốn đi nước ngoài thì ở trong nước cũng sẽ có rất nhiều điểm đẹp không thua kém bất cứ nơi nào trên thế giới. Bạn đã khám phá chưa?
Jinx: the Loose Cannon - Liên Minh Huyền Thoại
Jinx: the Loose Cannon - Liên Minh Huyền Thoại
Jinx, cô nàng tội phạm tính khí thất thường đến từ Zaun, sống để tàn phá mà chẳng bận tâm đến hậu quả.