-
Notifications
You must be signed in to change notification settings - Fork 0
/
HeapADT.c
96 lines (83 loc) · 2.41 KB
/
HeapADT.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
//filename : HeapADT.c
#include <stdio.h>
#include "HeapADT.h"
void CreateMaxHeap(HeapType *Heap)
/* Λειτουργία: Δημιουργεί ένα κενό σωρό.
Επιστρέφει: Ένα κενό σωρό
*/
{
(*Heap).Size=0;
}
boolean EmptyHeap(HeapType Heap)
/* Δέχεται: Ένα σωρό Heap.
Λειτουργία: Ελέγχει αν ο σωρός είναι κενός.
Επιστρέφει: TRUE αν ο σωρός είναι κενός, FALSE διαφορετικά
*/
{
return (Heap.Size==0);
}
boolean FullHeap(HeapType Heap)
/* Δέχεται: Ένα σωρό.
Λειτουργία: Ελέγχει αν ο σωρός είναι γεμάτος.
Επιστρέφει: TRUE αν ο σωρός είναι γεμάτος, FALSE διαφορετικά
*/
{
return (Heap.Size==MaxElements);
}
void InsertMaxHeap(HeapType *Heap, HeapNode Item)
/* Δέχεται: Ένα σωρό Heap και ένα στοιχείο δεδομένου Item .
Λειτουργία: Εισάγει το στοιχείο Item στο σωρό, αν ο σωρός δεν είναι γεμάτος.
Επιστρέφει: Τον τροποποιημένο σωρό.
Έξοδος: Μήνυμα γεμάτου σωρού αν ο σωρός είναι γεμάτος
*/
{
int hole;
if (!FullHeap(*Heap))
{
(*Heap).Size++;
hole=(*Heap).Size;
while (hole>1 && Item.key > Heap->Element[hole/2].key)
{
(*Heap).Element[hole]=(*Heap).Element[hole/2];
hole=hole/2;
}
(*Heap).Element[hole]=Item;
}
else
printf("Full Heap...\n");
}
void DeleteMaxHeap(HeapType *Heap, HeapNode *Item)
/* Δέχεται: Ένα σωρό Heap.
Λειτουργία: Ανακτά και διαγράφει το μεγαλύτερο στοιχείο του σωρού.
Επιστρέφει: Το μεγαλύτερο στοιχείο Item του σωρού και τον τροποποιημένο σωρό
*/
{
int parent, child;
HeapNode last;
boolean done;
if (!EmptyHeap(*Heap))
{
done=FALSE;
(*Item)=(*Heap).Element[1];
last=(*Heap).Element[(*Heap).Size];
(*Heap).Size--;
parent=1; child=2;
while (child<=(*Heap).Size && !done)
{
if (child<(*Heap).Size)
if ((*Heap).Element[child].key < (*Heap).Element[child+1].key)
child++;
if (last.key >= (*Heap).Element[child].key)
done=TRUE;
else
{
(*Heap).Element[parent]=(*Heap).Element[child];
parent=child;
child=2*child;
}
}
(*Heap).Element[parent]=last;
}
else
printf("Empty heap...\n");
}