תרגול #5

שיעור 14 מתוך 14 בקורס ערימות ותורי עדיפויות – סדרת מבני נתונים מס׳ 7 של Coddy.

אתגר

קל

כתבו פונקציה isMinHeap שמקבלת מערך של מספרים שלמים arr ומחזירה האם המערך מייצג ערימת מינימום תקינה.

מערך הוא ערימת מינימום כאשר כל צומת אב קטן או שווה לילדיו. באופן ספציפי, עבור כל אינדקס i בטווח, arr[i] <= arr[2*i + 1] (כאשר הילד השמאלי קיים) וגם arr[i] <= arr[2*i + 2] (כאשר הילד הימני קיים).

מערכים ריקים ומערכים בעלי איבר אחד הם ערימות מינימום בהגדרה.

עליכם להשתמש במחלקה MinHeap (שמסופקת בקובץ minheap.<ext>) — אל תשתמשו בפונקציות מובנות של השפה כמו sort או slice, או בספריות ערימה של stdlib כדי לחשב את התוצאה.

נסו בעצמכם

#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;
}