Hàng đợi có độ ưu tiên được ứng dụng rất nhiều trong các bài toán của hệ điều hành như lập lịch cho hệ thống, các hệ thống mô phỏng, hay chương trình dịch, và là nền tảng của nhiều thuật toán quan trọng. Các phương pháp khác nhau cài đặt hàng đợi có độ ưu tiên liên quan đến đặc điểm hoạt động của các thao tác. Chúng ta sẽ xét một cài đặt hàng đợi có độ ưu tiên bằng cấu trúc dữ liệu Heap. Cấu trúc này lưu trữ các đối tượng trong một mảng, bằng cách này mỗi khóa ở vị trí i đảm bảo lớn hơn hai khóa ở vị trí 2*i và 2*i+1(với ĐK: 1≤i≤2*i+1≤n) như hình 1. Thứ tự này của mảng cho ta thấy Heap có cấu trúc cây hai chiều, hay là một cây nhị phân hoàn chỉnh mà giá trị khóa ở nút cha bao giờ cũng lớn hơn khóa ở nút con của nó (hình 2). Dễ nhận thấy rằng biểu diễn mảng của Heap chính là kết quả của phép duyệt cây biểu diễn nó theo thứ tự tăng tầng.

Heap là cấu trúc dữ liệu trừu tượng, với bốn thao tác cơ bản là đưa một phần tử mới vào Heap (Insert), lấy ra phần tử có độ ưu tiên lớn nhất (Remove), đưa nút có khóa K về đúng vị trí theo chiều hướng đến gốc cây (Upheap), và đưa nút có khóa K về đúng vị trí theo chiều hướng đến ngọn (các nút lá) cây (Downheap). Chúng ta sẽ cài đặt cấu trúc dữ liệu Heap trong Free Pascal như là một kiểu dữ liệu. Ta tạo Unit Heap với nội dung như sau:

Unit Heap;

Interface

Type

Heap_type = object

Data:array[0..maxint] of integer;

Size: integer;

Procedure init; {phuong thc khoi tao heap}

Procedure upheap(vt: integer); {phuong thuc Upheap}

Procedure downheap(vt: integer); {phuong thuc Downheap}

Procedure insert(v: integer); {phuong thuc chen}

Function remove: integer; {phuong thuc loai bo}

End;

Implementation

{xay dung phuong thuc khoi tao Heap}

Procedure heap_type.init;

Begin

Fillchar(data,sizeof(data),0);

Size:=0;

Data[0]: = maxint; {gia tri canh}

End;

{Xay dung phuong thuc UpHeap}

Procedure heap_type.unheap(vt: integer);

Var key: integer;

Begin

Key:=data[vt];

While data[vt div 2]

Begin

data[vt]: = data[vt dic 2];

vt: = vt div 2;

end;

data[vt]: = key;

end;

{Xay dung phuong thuc DownHeap}

Procedure heap_type.downheap(vt: integer);

Var key, j : integer;

Begin

Key: = data[vt] ; j:=2*vt;

While j < = size do

Begin

If(j

If key > data[j] then

Begin

data[j div 2]: = key;

exit;

end

Else Begin

Data[j div 2]: = data[j];

J:=2*j;

End;

Data[j div 2]:= key;

End;

End;

{Xay dung phuong thuc chen mot phan tu moi vao Heap}

Procedure heap_type.insert(v: integer);

Begin

size: = size + 1;

data[size]:=v;

upheap(size);

end;

{Xay dung phuong thuc lay ra phan tu co do uu tien lon nhat}

Function heap_type.remove:integer;

Begin

Remove:= data[1]; data[1]: = data[size]; size:=size – 1;

Downheap(1);

End;

END. {end of unit}

Trên đây là toàn bộ chương trình nguồn của Unit Heap.Pas được viết trên Free Pascal sử dụng kỹ thuật lập trình hướng đối tượng. Các bạn hoàn toàn có thể cài đặt cài đặt Heap theo phương pháp lập trình cấu trúc truyền thống. Bằng cách khai báo Heap là một kiểu bản ghi Record, và chuyển các phương thức thành các hàm và thủ tục tương ứng.

Sau khi biên dịch Unit Heap.pas ta thu được tệp Heap.PPU. Nếu bạn biên dịch Unit trên trong Turbo Pascal thì ta thu được tệp Heap.TPU. Trong ví dụ sau ta sẽ áp dụng kiểu dữ liệu Heap để xây dựng một thuật toán sắp xếp – thuật toán Heap Sort.

Program Heap_Sort;

Uses crt; Heap; {khai bao unit Heap}

Var

A: array[0..200] of integer;

Lu, n, tg, I, tem: integer;

H: Heap_type; {Khai bao bien Heap}

Begin

Clrscr;

Write(‘ Nhap n’); readln(n);

For i:=1 to n do

Begin

Write(‘nhap a[‘, i , ‘] = ’); readln(a[i]);

End;

h.init; {khoi tao Heap}

{Dua du lieu tu mang vao Heap}

For i:=1 to n do

h.insert(a[i]);

{Tao heap}

For i:= h.size div 2 downto 1 do h.downheap(i);

Lu: = h.size;

Reppeat

Tg:= h.data[1];

h.data[1]: h.data[h.size]; h.data[h.size]:= tg;

h.size:=h.size – 1;

h.downheap(1);

Until h.size < = 1;

{xuat du lieu tu Heap ra mang}

h.size:= lu;

for i:=1 to lu do

a[i]:= h.data[i];

{Hien thi mang da sap xep}

For i:=1 to lu do

Write(a[i]:5);

Readln;

End.

Chúng ta vừa ứng dụng kiểu dữ liệu Heap để cài đặt thuật toán Heapsort. Đây là thuật toán sắp xếp hiệu quả và có tính ổn định cao. Bất chấp tính chất dữ liệu đầu vào, nó có độ phức tạp thuật toán là O(Nlog₂n). Ngoài ra ta còn có thể ứng dụng cấu trúc dữ liệu để xây dựng các thuật toán nén tệp tin, tìm kiếm cùng nhiều thuật toán bổ ích và lý thú khác.

School@net