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;