加载中...

   数据结构中的堆结构   

Knowledge Base

  • 完全二叉树:

​ 如果一棵深度为 $k$ 的二叉树,$1$ 至$ k-1$ 层的结点都是满的,即满足 $2^i-1$,只有最下面的一层的结点数小于$2^i-1$,并且最下面一层的结点都集中在该层最左边的若干位置,则此二叉树称为完全二叉树。

定义

​ 堆结构是一种数组对象,它可以被视为一棵完全二叉树。树中每个结点与数组中存放该结点中值的那个元素相对应,如下图:

Da1oSH.png

性质

  • 下标:

    ​ 第$i$个结点的父结点(parent(i))、左结点(left(i))、右结点(right(i))的下标分别为:$\frac {i}{2}$、$2i$、$2i+1$;

  • 大小:

    堆可以分为最大堆(max-heap)最小堆(min-heap)两种,分别满足对于任意的$i$, $A[parent(i)] >(<)A[i]$.

操作

src

//最小堆
class smallHeap {
public:
	int size, maxSize, * head = NULL;

	void init(int depth) {
        int p = qpow(2, depth, 19260817);
        head = new int[p-1];
        maxSize = p - 1;
	}

	smallHeap(int depth) {
		init(depth);
	}

	int getSize() {
		return size;
	}

	bool put(int val) {
		if (size == maxSize) return false;
		size++;
		int currentNode = size; head[currentNode] = val;
		while (currentNode != 1) {
			int parentNode = currentNode / 2;
			if (head[parentNode] > head[currentNode]) {
				int temp = head[parentNode];
				head[parentNode] = head[currentNode];
				head[currentNode] = temp;
				currentNode = parentNode;
			}
			else {
				break;
			}
		}
		return true;
	}

	int get() {
		int currentNode = 1;
		int tempValue = head[currentNode];
		head[currentNode] = head[size];
		size--;
		int parentNode = 1;
		while (1) {
			if (parentNode * 2 > size) break;
			currentNode = (head[parentNode * 2] < head[parentNode * 2 + 1]) ? (parentNode * 2) : (parentNode * 2 + 1);
			if (head[parentNode] > head[currentNode]) {
				int temp = head[parentNode];
				head[parentNode] = head[currentNode];
				head[currentNode] = temp;
				parentNode = currentNode;
			}
			else {
				break;
			}
		}

		return tempValue;
	}
    
    int top() { return head[1]; }

	void show() {
		for (int i = 1; i <= size; i++) {
			cout << head[i] << " ";
		}
	}
};

//最大堆
class bigHeap {
public:
	int size, maxSize, * head = NULL;

	void init(int depth) {
        int p = qpow(2, depth, 19260817);
        head = new int[p-1];
        maxSize = p - 1;
	}

	bigHeap(int depth) {
		init(depth);
	}

	int getSize() {
		return size;
	}

	bool put(int val) {
		if (size == maxSize) return false;
		size++;
		int currentNode = size; head[currentNode] = val;
		while (currentNode != 1) {
			int parentNode = currentNode / 2;
			if (head[parentNode] < head[currentNode]) {
				int temp = head[parentNode];
				head[parentNode] = head[currentNode];
				head[currentNode] = temp;
				currentNode = parentNode;
			}
			else {
				break;
			}
		}
		return true;
	}

	int get() {
		int currentNode = 1;
		int tempValue = head[currentNode];
		head[currentNode] = head[size];
		size--;
		int parentNode = 1;
		while (1) {
			if (parentNode * 2 > size) break;
			currentNode = (head[parentNode * 2] > head[parentNode * 2 + 1]) ? (parentNode * 2) : (parentNode * 2 + 1);
			if (head[parentNode] < head[currentNode]) {
				int temp = head[parentNode];
				head[parentNode] = head[currentNode];
				head[currentNode] = temp;
				parentNode = currentNode;
			}
			else {
				break;
			}
		}

		return tempValue;
	}
    
    int top() { return head[1]; }

	void show() {
		for (int i = 1; i <= size; i++) {
			cout << head[i] << " ";
		}
	}
};

Practice

Reference