97 lines
1.9 KiB
SAS
97 lines
1.9 KiB
SAS
%macro HeapInit(size=1000,nchar=20);
|
|
do;
|
|
_len = 0;
|
|
_size = &size;
|
|
array _times(&size) _temporary_ ;
|
|
array _kinds(&size) $ &nchar _temporary_;
|
|
drop _size _len;
|
|
end;
|
|
%mend;
|
|
%macro HeapSwapItem(index1, index2);
|
|
do;
|
|
_tempN = _times[&index1]; _times[&index1] = _times[&index2]; _times[&index2] = _tempN;
|
|
_tempC = _kinds[&index1]; _kinds[&index1] = _kinds[&index2]; _kinds[&index2]= _tempC;
|
|
drop _tempN _tempC;
|
|
end;
|
|
%mend;
|
|
%macro HeapEmpty;
|
|
(_len=0)
|
|
%mend;
|
|
%macro HeapCompare(index1, index2);
|
|
(_times[&index1] < _times[&index2])
|
|
%mend;
|
|
%macro HeapSiftdown(index);
|
|
do;
|
|
_parent = &index;
|
|
_done = 0;
|
|
do while (_parent*2 <= _len & ^_done);
|
|
_child = _parent*2;
|
|
if (_child+1 <= _len and %HeapCompare(_child+1,_child)) then
|
|
_child = _child + 1;
|
|
if %HeapCompare(_child,_parent) then do;
|
|
%HeapSwapItem(_child,_parent);
|
|
_parent = _child;
|
|
end;
|
|
else _done = 1;
|
|
end;
|
|
drop _done _parent _child;
|
|
end;
|
|
%mend;
|
|
%macro HeapSiftup(index);
|
|
do;
|
|
_child = &index;
|
|
_done = 0;
|
|
do while(_child>1 and ^_done);
|
|
_parent = floor(_child/2);
|
|
if %HeapCompare(_parent,_child) then
|
|
_done = 1;
|
|
else do;
|
|
%HeapSwapItem(_child,_parent);
|
|
_tempN = _child;
|
|
_child = _parent;
|
|
_parent = _tempN;
|
|
end;
|
|
end;
|
|
drop _parent _child _done _tempN;
|
|
end;
|
|
%mend;
|
|
%macro HeapPush(time, kind);
|
|
do;
|
|
if _len >= _size then do;
|
|
put "ERROR: exceeded size of heap. Consider changing size argument to %HeapInit.";
|
|
stop;
|
|
end;
|
|
_len = _len + 1;
|
|
_times[_len] = &time;
|
|
_kinds[_len] = &kind;
|
|
%HeapSiftup(_len);
|
|
end;
|
|
%mend;
|
|
%macro HeapPop;
|
|
do;
|
|
_len = _len - 1;
|
|
if (_len>0) then do;
|
|
_times[1] = _times[_len+1];
|
|
_kinds[1] = _kinds[_len+1];
|
|
%HeapSiftdown(1);
|
|
end;
|
|
end;
|
|
%mend;
|
|
%macro HeapPeek;
|
|
time = _times[1];
|
|
kind = _kinds[1];
|
|
put time kind;
|
|
%mend;
|
|
data _null_;
|
|
%HeapInit;
|
|
%HeapPush(3, "Clear drains");
|
|
%HeapPush(4, "Feed cat");
|
|
%HeapPush(5, "Make tea");
|
|
%HeapPush(1, "Solve RC tasks");
|
|
%HeapPush(2, "Tax return");
|
|
do while(^%HeapEmpty);
|
|
%HeapPeek;
|
|
%HeapPop;
|
|
end;
|
|
run;
|