最も多くの実装(最も基本的な機能)

アルゴリズム導論上のスタックソートアルゴリズムを参照して、以下の最大スタック(採用されたデータ構造は配列)を実現した.最も基本的な機能のみがあり、最後にこの最大スタックを利用してスタックソート(非減算ソート)を実現した.コードは以下の通りである.
max_heap_sort.h:

#define PARENT(i) ((i - 1)/2)
#define LEFT(i) (2*i + 1)
#define RIGHT(i) (2*i + 2)

void max_heapify(vector<int> & vec_ints, int heap_size, int i);
void build_max_heap(vector<int> & vec_ints, int heap_size);
void max_heap_sort(vector<int> & vec_ints);

max_heap_sort.cpp:

void max_heapify(vector<int> & vec_ints, int heap_size, int i)
{
	int largest = -1;
	int l = LEFT(i);
	int r = RIGHT(i);

	if (l < heap_size && vec_ints[l] > vec_ints[i])
	{
		largest = l;
	} 
	else
	{
		largest = i;
	}

	if (r < heap_size && vec_ints[r] > vec_ints[largest])
	{
		largest = r;
	}

	if (largest != i)
	{
		swap(vec_ints[i], vec_ints[largest]);
		max_heapify(vec_ints, heap_size, largest);
	}
}

void build_max_heap(vector<int> & vec_ints, int heap_size)
{
	int s = PARENT(heap_size - 1);
	for (int i = s; i >=0; i--)
	{
		max_heapify(vec_ints, heap_size, i);
	}
}

void max_heap_sort(vector<int> & vec_ints)
{
	int heap_size = vec_ints.size();
	build_max_heap(vec_ints, heap_size);
	for (int i = vec_ints.size() - 1; i > 0; i--)
	{
		swap(vec_ints[i], vec_ints[0]);
		heap_size--;
		max_heapify(vec_ints, heap_size, 0);
	}
}