Bài thực hành số 8. CẤU TRÚC HEAP môn Tin học đại cương | Đại học Bách Khoa Hà Nội

Bài thực hành số 8. CẤU TRÚC HEAP
Mục tiêu: vận dụng cấu trúc heap trong hàng đợi ưu tiên và cài đặt thuật toán heapsort.
Nội dung thực hành:
Bài 1. Hàng đợi ưu tiên bằng Heap
Cài đặt hàng đợi ưu tiên sử dụng Heap, trong đó khóa của heap là độ ưu tiên của phần tử trong hàng đợi.
Minh họa một hàng đợi ưu tiên mà dữ liệu là 1 ký tự. Độ ưu tiên là một số nguyên. Tổ chức dữ liệu: #define max 100 struct Element { char data; int priority; }; struct PriorityQueue { Element arr[max]; int size; }; a) Thao tác thêm vào:
Thêm một phần tử vào cuối hàng đợi
Dùng thao tác siftUp để chỉnh hàng đợi vừa thêm thành heap.
Thao tác siftUp thực hiện chỉnh một cây nhị phân đầy đủ mà bỏ phần tử cuối đi là heap. void siftUp(PriorityQueue *q) { int i,p; Element tmp; i = q->size-1; while(i > 0) { p = (i-1)/2;
if (q->arr[p].priority < q->arr[i].priority) { tmp = q->arr[p]; q->arr[p] = q->arr[i]; q->arr[i] = tmp; 102 i = p; } else return; } }
void add(PriorityQueue *q, Element x) { q->arr[q->size] = x; q->size++; siftUp(q); } b) Thao tác lấy ra:
- Lấy ra phần tử ở đỉnh heap
- Đưa phần tử ở cuối hàng đợi lên đầu
- Dùng siftDown để hiệu chỉnh hàng đợi sau khi lấy ra thành heap.
void siftDown(PriorityQueue *q) { int p = 0, i = 2*p + 1; while (i < q->size) {
if (i+1 size && q->arr[i].priorityarr[i+1].priority) i = i + 1;
if (q->arr[p].priority < q->arr[i].priority) { Element tmp = q->arr[p]; q->arr[p] = q->arr[i]; q->arr[i] = tmp; p = i; i = 2*p + 1; } else return; } }
Element remove(PriorityQueue *q) { int n; Element x; 103 n = q->size; x = q->arr[0];
q->arr[0] = q->arr[n-1]; q->size--; siftDown(q); return x; } Chương trình chính: int main() { PriorityQueue q; Element x; q.size = 0; add(&q, {'A', 3}); add(&q, {'B', 4}); add(&q, {'C', 1}); x = remove(&q);
cout << x.data << " " << x.priority << endl; x = remove(&q);
cout << x.data << " " << x.priority << endl; }
Thêm các phần tử vào hàng đợi ưu tiên có cùng độ ưu tiên rồi lấy các phần tử
này ra và in kết quả lên màn hình. Bổ sung các hàm:
c) Kiểm tra một hàng đợi ưu tiên có rỗng không? bool isEmpty(PriorityQueue q) { }
d) Trả về phần tử đầu tiên của hàng đợi ưu tiên, không lấy ra khỏi hàng đợi. Element top(PriorityQueue q) { } 104 Bài 2. HeapSort
Cài đặt thuật toán HeapSort trên mảng các số nguyên. Sử dụng các thuật toán
trên Heap hãy cài đặt thuật toán sắp xếp theo kiểu vun đống (HeapSort) theo gợi ý sau:
Hàm siftDown chỉnh cây nhị phân đầy đủ lưu trong mảng arr từ vị trí i đến vị trí
n mà mọi cây con đều là heap thành heap.
// Function to sift down the element at index i
void siftDown(int arr[], int i, int n) { int maxIndex = i; int left = 2*i + 1; int right = 2*i + 2;
if (left < n && arr[left] > arr[maxIndex]) maxIndex = left;
if (right < n && arr[right] > arr[maxIndex]) maxIndex = right; if (i != maxIndex) { swap(arr[i], arr[maxIndex]); siftDown(arr, maxIndex, n); } }
Hàm sắp xếp mảng arr có n phần tử. Theo thuật toán: - Tạo heap từ mảng arr - Lặp n-1 lần:
+ Đổi phần tử ở đỉnh của heap với phần tử cuối
+ Thực hiện sifDown cho mảng với số phần tử giảm đi 1
// Main function to perform Heap Sort
void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--) siftDown(arr, i, n); 105
// One by one extract an element from heap
for (int i = n - 1; i >= 0; i--) { // Move current root to end swap(arr[0], arr[i]);
// Call siftDown on the reduced heap siftDown(arr, 0, i); } }
Viết chương trình sinh ngẫu nhiên mảng n phần tử rồi sắp xếp bằng thuật toán HeapSort. #include
void randomArr(int a[], int n) { int i; for(i = 0; i < n; i++) a[i] = rand(); } // Driver code int main() { int arr[1000], n = 1000; srand(time(NULL)); randomArr(arr,n); heapSort(arr, n);
cout << "Sorted array is \n";
for (int i = 0; i < n; ++i)
cout << arr[i] << " "; return 0; }
Tạo mảng các sinh viên gồm họ tên và điểm trung bình. Sắp xếp mảng theo thứ
tự giảm của điểm trung bình. 106
Bài 3. Sử dụng hàng đợi ưu tiên trong thư viện C++
Trong thư viện STL với header của C++ cài đặt lớp priority_queue cho
hàng đợi ưu tiên với khả năng sử dụng phong phú. Khai báo biến:
std::priority_queue variable; hàng đợi ưu tiên các phần tử
có kiểu DataType và kiểu dữ liệu đã có phép toán so sánh >, <. Ví dụ: std::priority_queue pq;
Với kiểu dữ liệu cần định nghĩa phép so sánh có thể dùng:
std::priority_queue, compare> variable; trong đó
compare là cách so sánh các phần tử trong hàng đợi ưu tiên. Ví dụ:
std::priority_queue, greater > pq;
Dùng để tạo hàng đợi ưu tiên với thứ tự tăng.
Tạo hàng đợi ưu tiên mỗi phần tử là một sinh viên, thứ tự theo điểm trung bình tăng: struct Student{ string name; int age; float gpa; }; struct CompareGPA {
bool operator()(const Student& a, const Student& b) { return a.gpa > b.gpa; } };
std::priority_queue, CompareGPA) pd; Các phương thức:
push(element): thêm một phần tử vào hàng đợi ưu tiên
pop(): xóa một phần tử có độ ưu tiên cao nhất
top(): trả về phần tử có độ ưu tiên cao nhất
empty(): kiểm tra hàng đợi ưu tiên có rỗng không
size(): trả về số phần tử của hàng đợi ưu tiên.
Ví dụ 1. Chương trình minh họa đưa các phần tử của mảng số nguyên vào hàng
đợi ưu tiên rồi lấy ra và in lên màn hình. 107 // geeksforgeeks.org
// C++ program to demonstrate the use of priority_queue #include #include using namespace std; // driver code int main() {
int arr[6] = { 10, 2, 4, 8, 6, 9 }; // defining priority queue priority_queue pq; // printing array cout << "Array: "; for (auto i : arr) {
cout << i << ' '; } cout << endl;
// pushing array sequentially one by one
for (int i = 0; i < 6; i++) { pq.push(arr[i]); } // printing priority queue
cout << "Priority Queue: "; while (!pq.empty()) {
cout << pq.top() << ' '; pq.pop(); } return 0; }
a) Hãy sửa chương trình trên để hàng đợi ưu tiên sắp theo thứ tự tăng. 108
b) Hãy bổ sung vào chương trình trên sao cho hàng đợi ưu tiên lấy các số chẵn trước
các số lẻ với các số cùng chẵn hay lẻ thì lấy số lớn trước.
Ví dụ 2. Chương trình minh họa thao tác tạo một hàng đợi ưu tiên các sinh viên theo điểm trung bình. #include #include using namespace std; struct Student { string name; int age; float gpa; }; struct CompareGPA {
bool operator()(const Student& a, const Student& b) { return a.gpa > b.gpa; } }; int main() {
std::priority_queue, CompareGPA> pq;
Student s1 = {"Alice", 20, 3.8};
Student s2 = {"Bob", 22, 3.5};
Student s3 = {"Charlie", 21, 4.0}; pq.push(s1); pq.push(s2); 109 pq.push(s3); while (!pq.empty()) { Student top = pq.top();
std::cout << top.name << " " << top.age << " " << top.gpa << std::endl; pq.pop(); } return 0; }
Hãy bổ sung các cách so sánh:
a) Tuổi theo thứ tự giảm b) Tên theo thứ tự tăng ------------------- 110