Luyện tập #4
Bài học 13 trên 14 trong khóa học Heap và hàng đợi ưu tiên: loạt bài về cấu trúc dữ liệu #7 của Coddy.
Thử thách
DễViết một hàm (function) heapSort nhận một mảng số nguyên arr và trả về mảng đã được sắp xếp theo thứ tự tăng dần.
heapSort là ứng dụng điển hình của heap tối thiểu: chèn từng giá trị vào heap, sau đó lấy giá trị nhỏ nhất ra cho đến khi heap rỗng.
Bạn phải dùng lớp MinHeap (được cung cấp trong minheap.<ext>), không dùng các hàm có sẵn của ngôn ngữ như sort, slice hoặc thư viện heap của thư viện chuẩn để tính kết quả.
Tự làm thử
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include "solution.h"
int main() {
char line[8192];
if (!fgets(line, sizeof(line), stdin)) line[0] = '\0';
int arr[4096];
int n = 0;
char* tok = strtok(line, " \t\r\n");
while (tok) { arr[n++] = atoi(tok); tok = strtok(NULL, " \t\r\n"); }
int rs = 0;
int* r = heapSort(arr, n, &rs);
for (int idx = 0; idx < rs; idx++) { if (idx > 0) printf(" "); printf("%d", r[idx]); }
printf("\n");
return 0;
}
Tất cả bài học trong Heap và hàng đợi ưu tiên: loạt bài về cấu trúc dữ liệu #7
Tự luyện tập: Trình biên dịch C online