Thuật toán Heap Sort (Sắp xếp vun đống)

Giới thiệu Heap

Trong khoa học máy tính, Heap là một cấu trúc dữ liệu dựa trên cây thỏa mãn tính chất đống, là một trường hợp đặc biệt của cây nhị phân cân bằng thỏa mãn: nếu B là nút con của A thì giá trị khóa của (A) ≥ giá trị khóa của (B). Một hệ quả của tính chất này là giá trị khóa lớn nhất luôn nằm ở nút gốc. Do đó một Heap như vậy thường được gọi là Max Heap. Nếu mọi phép so sánh bị đảo ngược khiến cho khóa có giá trị nhỏ nhất luôn nằm ở nút gốc thì đống đó gọi là min heap. Heap có vai trò quan trọng trong nhiều thuật toán cho đồ thị chẳng hạn như thuật toán Dijkstra, hay thuật toán sắp xếp Heap Sort.

Link Video: Giới thiệu heap (Introduction)

Để hiểu rõ hơn về cấu trúc heap các bạn có thể tham khảo thêm nguồn tài liệu sau:

Linh Page: Giới thiệu heap ( Introduction to heap)

Xóa nút gốc

Mặc dù tương tự như cây nhị phân cân bằng nhưng Heap có những ràng buộc riêng của nó, vậy làm thế nào để duy trì các ràng buộc này khi chúng ta cần thêm vào / xóa bỏ một phần tử trên Heap. Các bạn hãy xem video này để xem thao tác khi xóa đi một phần tử trên heap

Link Video: Xóa nút gốc (Deleting the root)

Chèn 1 phần tử vào heap

Các bạn hãy xem thao tác khi chèn thêm một phần tử trong heap thông qua video này

Link Video: Chèn một phần tử vào heap ( Inserting an item in a heap)

Sử dụng heap để xây dựng hàng đợi ưu tiên

Sử dụng heap để xây dựng hàng đợi ưu tiên (phần tử có độ ưu tiên cao hơn được ra trước, không tuân theo FIFO). Video sẽ mô tả điều này

Link Video: Sử dụng heap xây dựng hàng đợi ưu tiên ( Heaps as Priority Queues)

Biểu diễn heap bằng mảng

Một Heap hoàn toàn có thể được biểu diễn bằng mảng 1 chiều, sao cho thứ tự lưu trữ của các item trong mảng tương ứng với cây nhị phân là từ root - > left, từ left children -> right children, các node trên cây khi đặt vào mảng theo tiêu chí sau:

Root có index i = 0 (node root trong cây khi đặt vào mảng là phần tử đầu tiên trong mảng)

Parent (i) = i/2 (i/2 sẽ là chỉ số node cha của node có chỉ số i ở trong mảng)

Left(i) = 2i ( 2i sẽ là chỉ số node con trái của node có chỉ số i ở trong mảng)

Right(i) = 2i+1 (2i+1 sẽ là chỉ số node con trái của node có chỉ số i ở trong mảng)

Link Video: Biểu diễn heap bằng mảng (repsenting heaps using arays)

Thuật toán sắp xếp vun đống (Heap Sort)

Thuật toán Heap Sort vận hành dựa trên cấu trúc Heap.

Link video: Thuật toán sắp xếp vun đống (Heap Sort)

Xây dựng một heap

Video sau sẽ mô tả việc xây dựng một heap thông qua ví dụ

Link Video: Xây dựng một heap (building a heap)

Cài đặt code bằng Java cho heap sort

import java.util.*;
class EffSort
{int [] a; int n;
EffSort() {}
EffSort(int [] b)
   {int i;
    n = b.length;
    a = new int[n];
    for(i=0;i<n;i++) a[i]= b[i];
   }

// Set dữ liệu cho mảng
void setData(int [] b)
   {int i;
    n = b.length;
    a = new int[n];
    for(i=0;i<n;i++)
       a[i]= b[i];
   }
void display()
   {int i;
    for(i=0;i<n;i++)
      System.out.print(" " + a[i]);
    System.out.println();
   }
//==================================================
/*Sap xep bang HEAP: Heap la cay nhi phan gan day duoc cai dat bang
    mang mot chieu voi cac nut tren heap co noi dung nho hon nut goc
    va cac nhanh cay con cung la cac heap
*/
void heapSort()
   {/*Chuyen danh sach thanh HEAP bang cach xem khoi dau heap gom nut
      a[0], sau do lan luot chuyen cac nut a[1],a[2],...,
      a[n-1] vao heap*/
    int i,s,f;int x;
    for(i=1;i<n;i++)
     {x=a[i];//Nut can them vao HEAP, ban dau heap co mot nut a[0].
          /*Insert x vao vi tri thich hop cua HEAP: xuat phat tu i, di dan ve
            goc de tim mot vi tri nut cha thich hop. Vay f se giam dan
          */
      s=i; //s la nut con, hien tai tren heap chua co a[i]
       //f=(s-1)/2 la nut cha
      while(s>0 && x>a[(s-1)/2])
        {a[s]=a[(s-1)/2]; //Keo nut < x xuong 1 muc
         s=(s-1)/2;
        };
      a[s]=x; //Dua nut x vao vi tri phu hop
     };
    //Ket thuc chuyen danh sach thanh heap
    System.out.println(" Heap:");
    display();
    //Lan luot xoa nut a[0] tren HEAP, dua ve vi tri thich hop tren ds
    for(i=n-1;i>0;i--)
     {x=a[i];a[i]=a[0];
      /*O buoc i heap co i+1 nut, la a[0], a[1],...,a[i]
        Muc dich cua chung ta la dua nut a[0] ve vi tri a[i],
        dong thoi, chen a[i] vao heap sao cho cau truc heap van bao
        toan. De lam dieu nay ta bat dau tu
        nut f = 0, theo con duong cha - con trai hoac phai, tim mot vi tri
        de chen nut a[i]. De co duoc nut trong de chen a[i], ta can
        dich cac nut tren duong di len mot muc, bang cong thuc
        nutgoc=max(contrai,conphai,a[i])
      */
      f=0; //f la nut cha, s la nut con lon hon
      s=2*f+1; //Gan s la nut con ben trai
      if(s+1<i && a[s]<a[s+1]) s=s+1;/*Neu co nut phai va
     lon hon thi chon nut phai*/
      while(s<i && x<a[s])
       {a[f]=a[s];//Con lon thay the cha
f=s;//Chuyen den con lon tiep theo
s=2*f+1;
if(s+1<i && a[s]<a[s+1]) s=s+1;
       };
       a[f]=x; //Nut a[k] duoc chen dung cho
     };
   };
}
//==================================================
public class Main
{public static void main(String args[])
   {int [] b = {7,3,5,9,11,8,6,15,10,12,14};
    EffSort t = new EffSort(b);
    t.heapSort();t.display();
    System.out.println();
   }
}

**************************

Bài tập thực hành

Hãy viết chương trình cài đặt một HeapSort bằng mảng, sau đó hãy hiển thị tất cả các phần tử trong HeapSort ra màn hình. Giả sử rằng các phần tử đầu vào của Heap sort là mảng a[]= {7,3,5,9,11,8,6,15,10,12,14}.

Gợi ý:

- Gợi ý về Input, Output:

Input:

Mảng a với các giá trị cụ thể:

a[]=7,3,5,9,11,8,6,15,10,12,14;

Output: 3 5 6 7 8 9 10 11 12 14 15

- Chương trình gồm có các lớp và các hàm cơ bản sau, các bạn hoàn toàn có thể thêm lớp, các hàm nếu cảm thấy cần thiết hoặc có thể làm bằng cách khác

class EffSort
{int [] a; int n;
EffSort() {}
EffSort(int [] b)
   {int i;
    n = b.length;
    a = new int[n];
    for(i=0;i<n;i++) a[i]= b[i];
   }

void display()
   {int i;
    for(i=0;i<n;i++)
      System.out.print(" " + a[i]);
    System.out.println();
   }
//==================================================
/*Sap xep bang HEAP: Heap la cay nhi phan gan day duoc cai dat bang
    mang mot chieu voi cac nut tren heap co noi dung nho hon nut goc
    va cac nhanh cay con cung la cac heap
*/
void heapSort()
   {…………..
}}
//==================================================
public class Main
{public static void main(String args[])
   {int [] b = {7,3,5,9,11,8,6,15,10,12,14};
    EffSort t = new EffSort(b);
    t.heapSort();t.display();
    System.out.println();
   }
}

Cùng Học IT