二叉堆

二叉堆C++实现

class BinaryHeap
{
public:
	void push(int v);
	int pop();
	int get_heap_size() { return binary_heap.size(); }
	int peak_top() { return index_at(1); };
	int index_at(int i) { return binary_heap[i - 1]; }
	void set_at(int i, int v) { binary_heap[i - 1] = v; };
private:
	void adjust_heap(int idx);
	void adjust_heap_down(int idx);
	int compare(int left, int right);

	std::vector<int> binary_heap = {};
	static int index;
};

int BinaryHeap::index = 0;


// 往二叉堆中插入元素
void BinaryHeap::push(int v)
{
	binary_heap.push_back(v);
	index++;

	if (binary_heap.size() == 1)
		return;
	
	// 调整堆
	adjust_heap(index);
}

// 获取二叉堆中的堆顶元素
int BinaryHeap::pop()
{
	if (!binary_heap.size()) return -1;

	// 将最后一个叶子节点换到头节点
	int ret = index_at(1);
	binary_heap[1] = index_at(index);

	adjust_heap_down(1);

	return ret;
}

// 调整堆
void BinaryHeap::adjust_heap(int idx)
{
	int root;
	int tmp;

	while ((root = idx / 2) > 0 && compare(index_at(idx), index_at(root)) < 0)
	{
		tmp = index_at(idx);
		set_at(idx, index_at(root));
		set_at(root, tmp);

		idx = root;
	}


}

// 向下调整堆
void BinaryHeap::adjust_heap_down(int idx)
{
	int lchild;
	int tmp;

	while ((lchild = 2 * idx) <= index)
	{
		if (lchild + 1 <= index && compare(index_at(lchild + 1), index_at(lchild)) < 0)
			lchild = lchild + 1;
		
		if (compare(index_at(lchild), index_at(idx)))
		{
			tmp = index_at(idx);
			set_at(idx, index_at(lchild));
			set_at(lchild, tmp);
		}

		idx = lchild;
	}
}

// 比较器
int BinaryHeap::compare(int l, int r)
{
	return l - r;
}

int main()
{
	BinaryHeap binaryh;
	binaryh.push(12);
	binaryh.push(17);
	binaryh.push(11);

	std::cout << binaryh.peak_top() << std::endl;


}