Luyện tập #5
Bài học 14 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 isMinHeap nhận một mảng số nguyên arr và trả về liệu mảng đó có biểu diễn một đống min hợp lệ hay không.
Một mảng là đống min khi mỗi nút cha nhỏ hơn hoặc bằng các nút con. Cụ thể, với mọi chỉ số i trong phạm vi, arr[i] <= arr[2*i + 1] (khi có nút con bên trái) và arr[i] <= arr[2*i + 2] (khi có nút con bên phải).
Theo định nghĩa, mảng rỗng và mảng chỉ có một phần tử đều là đống min.
Bạn phải sử dụng lớp MinHeap (được cung cấp trong minheap.<ext>) — không dùng các hàm dựng sẵn của ngôn ngữ như sort, slice hoặc thư viện heap trong 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"); }
bool r = isMinHeap(arr, n);
printf("%s\n", r ? "true" : "false");
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