Блок задач

3. Структуры данных

Темы
Сложность 5

Задача «Очередь с приоритетом»

Реализовать очередь с приоритетом на базе двоичной кучи.

typedef void *Pointer;
typedef int (*CmpFunc)(Pointer data1, Pointer data2);

typedef struct tPriorityQueue {
    /* ... */
} PriorityQueue;

/* Create empty priority queue. */
void pq_create(PriorityQueue *pq, CmpFunc cmp);

/* Destroy priority queue and free its memory. */
void pq_destroy(PriorityQueue *pq);

/* Add new value into the priority queue. */
void pq_insert(PriorityQueue *pq, Pointer value);

/* Delete maximum value from the priority queue and return it. */
Pointer pq_delete_maximum(PriorityQueue *pq);

/* Return non-zero value if the priority queue is not empty. */
int pq_is_empty(PriorityQueue *pq);

Во-первых, необходимо реализовать тесты через assert.

Во-вторых, необходимо реализовать интерактивную программу "TODO-list". Пользователь:

  • либо добавляет новое дело, имеющее название (одно слово) и приоритет (целое число),
  • либо запрашивает дело с максимальным приоритетом из списка дел и делает его.