111 lines
2.6 KiB
SAS
111 lines
2.6 KiB
SAS
proc ds2;
|
|
package Heap / overwrite=yes;
|
|
dcl int _entryorder _size _len _entryOrders[1000];
|
|
dcl double _times[1000];
|
|
dcl varchar(20) _kinds[1000];
|
|
method init();
|
|
_entryOrder = 1;
|
|
_size = 1000;
|
|
_len = 0;
|
|
end;
|
|
method empty() returns int;
|
|
return(_len=0);
|
|
end;
|
|
method compare(int index1, int index2) returns int;
|
|
return(_times[index1] < _times[index2] or (_times[index1] = _times[index2] and _entryOrders[index1] < _entryOrders[index2]));
|
|
end;
|
|
method SetItem(int index, double _time, int entryOrder, varchar(20) kind);
|
|
_times[index] = _time;
|
|
_entryOrders[index] = entryOrder;
|
|
_kinds[index] = kind;
|
|
end;
|
|
method CopyItem(int ito, int ifrom);
|
|
_times[ito] = _times[ifrom];
|
|
_entryOrders[ito] = _entryOrders[ifrom];
|
|
_kinds[ito] = _kinds[ifrom];
|
|
end;
|
|
method SwapItem(int index1, int index2);
|
|
dcl double tempD;
|
|
dcl int tempI;
|
|
dcl varchar(20) tempC;
|
|
tempD = _times[index1]; _times[index1] = _times[index2]; _times[index2]= tempD;
|
|
tempI = _entryorders[index1]; _entryorders[index1] = _entryorders[index2]; _entryorders[index2]= tempI;
|
|
tempC = _kinds[index1]; _kinds[index1] = _kinds[index2]; _kinds[index2]= tempC;
|
|
end;
|
|
method Siftdown(int index);
|
|
dcl int parent done child;
|
|
parent = index;
|
|
done = 0;
|
|
do while (parent*2 <= _len and ^done);
|
|
child = parent*2;
|
|
if (child+1 <= _len and Compare(child+1,child)) then
|
|
child = child + 1;
|
|
if Compare(child,parent) then do;
|
|
SwapItem(child,parent);
|
|
parent = child;
|
|
end;
|
|
else done = 1;
|
|
end;
|
|
end;
|
|
method Siftup(int index);
|
|
dcl int parent child done tempI;
|
|
child = index;
|
|
done = 0;
|
|
do while(child>1 and ^done);
|
|
parent = floor(child/2);
|
|
if Compare(parent,child) then
|
|
done = 1;
|
|
else do;
|
|
SwapItem(child,parent);
|
|
tempI = child;
|
|
child = parent;
|
|
parent = tempI;
|
|
end;
|
|
end;
|
|
end;
|
|
method Pop();
|
|
_len = _len - 1;
|
|
if (_len>0) then do;
|
|
CopyItem(1,_len+1);
|
|
Siftdown(1);
|
|
end;
|
|
end;
|
|
method PeekTime() returns double;
|
|
return _times[1];
|
|
end;
|
|
method PeekKind() returns varchar(20);
|
|
return _kinds[1];
|
|
end;
|
|
method Push(double _time, varchar(20) kind);
|
|
if _len >= _size then do;
|
|
put 'ERROR: exceeded size of heap.';
|
|
stop;
|
|
end;
|
|
_len = _len + 1;
|
|
_entryOrder = _entryOrder + 1;
|
|
SetItem(_len, _time, _entryOrder, kind);
|
|
Siftup(_len);
|
|
end;
|
|
endpackage;
|
|
run;
|
|
data _null_;
|
|
dcl package Heap h();
|
|
method init();
|
|
dcl double _time;
|
|
dcl varchar(20) _kind;
|
|
h.init();
|
|
h.Push(3, 'Clear drains');
|
|
h.Push(4, 'Feed cat');
|
|
h.Push(5, 'Make tea');
|
|
h.Push(1, 'Solve RC tasks');
|
|
h.Push(2, 'Tax return');
|
|
do while(^h.empty());
|
|
_time = h.PeekTime();
|
|
_kind = h.PeekKind();
|
|
put _time _kind;
|
|
h.Pop();
|
|
end;
|
|
end;
|
|
enddata;
|
|
run;
|