-
Notifications
You must be signed in to change notification settings - Fork 0
/
PriorityQueue.m
88 lines (80 loc) · 1.88 KB
/
PriorityQueue.m
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
//
// PriorityQueue.m
// DCTimer
//
// Created by meigen on 15/10/31.
//
//
#import "PriorityQueue.h"
#import "FullCube.h"
@implementation PriorityQueue
@synthesize queue;
-(id) init {
if (self = [super init]) {
queue = [[NSMutableArray alloc] init];
size = 0;
}
return self;
}
-(void) clear {
[queue removeAllObjects];
size = 0;
}
-(NSMutableArray *)toArray {
if (queue.count > size) {
for (int i=size; i<queue.count; i++)
[queue removeObjectAtIndex:i];
}
return queue;
}
-(int)size {
return size;
}
-(FullCube *) poll {
if (queue.count == 0) {
return nil;
}
int s = --size;
FullCube *res = [queue objectAtIndex:0];
FullCube *x = [queue objectAtIndex:s];
int half = s >> 1;
int k = 0;
while(half > k) {
int child = (k << 1) + 1;
FullCube *c = [queue objectAtIndex:child];
int right = child + 1;
FullCube *cr = [queue objectAtIndex:right];
if (right < s && c->value < cr->value)
c = [queue objectAtIndex:(child = right)];
if (x->value >= c->value) break;
[queue replaceObjectAtIndex:k withObject:c];
k = child;
}
[queue replaceObjectAtIndex:k withObject:x];
return res;
}
-(BOOL) add:(FullCube *)x {
if (x == nil) {
return NO;
}
int k = size;
if (k == 0)
[queue addObject:x];
else {
while (k > 0) {
int parent = (k - 1) >> 1;
FullCube *e = [queue objectAtIndex:parent];
if(x->value <= e->value) break;
if (k >= queue.count)
[queue addObject:e];
else [queue replaceObjectAtIndex:k withObject:e];
k = parent;
}
if (k >= queue.count)
[queue addObject:x];
else [queue replaceObjectAtIndex:k withObject:x];
}
size++;
return YES;
}
@end