Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <time.h>
- #include <string.h>
- #pragma warning (disable:4996)
- #define LCHILD(x) 2 * x + 1
- #define RCHILD(x) 2 * x + 2
- #define PARENT(x) (x - 1) / 2
- typedef struct node {
- int hodnota;
- char meno[1000];
- } node;
- typedef struct maxHeap {
- int size;
- node *elem;
- } maxHeap;
- maxHeap *tree = NULL;
- void initMaxHeap() {
- int size = 1000000;
- tree = malloc(sizeof(maxHeap));
- tree->size = 0;
- tree->elem = malloc(size * sizeof(node));
- return;
- }
- void swap(node *n1, node *n2) {
- node temp = *n1;
- *n1 = *n2;
- *n2 = temp;
- }
- void heapify(int i) {
- int largest = (LCHILD(i) < tree->size && tree->elem[LCHILD(i)].hodnota > tree->elem[i].hodnota) ? LCHILD(i) : i;
- if (RCHILD(i) < tree->size && tree->elem[RCHILD(i)].hodnota > tree->elem[largest].hodnota) {
- largest = RCHILD(i);
- }
- if (largest != i) {
- swap(&(tree->elem[i]), &(tree->elem[largest]));
- heapify(largest);
- }
- }
- void vloz(char *meno, int data) {
- node *nd = (node *)malloc(sizeof(node));
- nd->hodnota = data;
- strcpy(nd->meno, meno);
- int i = (tree->size)++;
- while (i && nd->hodnota > tree->elem[PARENT(i)].hodnota) {
- tree->elem[i] = tree->elem[PARENT(i)];
- i = PARENT(i);
- }
- tree->elem[i] = *nd;
- }
- void deleteNode() {
- if (tree->size) {
- printf("%s\n", tree->elem[0].meno);
- tree->elem[0] = tree->elem[--(tree->size)];
- tree->elem = realloc(tree->elem, tree->size * sizeof(node));
- heapify(0);
- }
- else {
- free(tree->elem);
- }
- return;
- }
- void *vyber_najvyssie() {
- deleteNode();
- return 0;
- }
- int main() {
- char buf[1000];
- int x;
- initMaxHeap();
- while (scanf("%s", buf) > 0) {
- if (!strcmp(buf, "vyber"))
- vyber_najvyssie();
- else {
- scanf("%s %d", buf, &x);
- vloz(buf, x);
- }
- if (tree->size == 0) {
- initMaxHeap();
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement