树节点实现堆

Posted on | In
利用树节点实现一个堆

构建堆的树节点

用于构建堆的树节点需要有如下几个属性：

  • value 值
  • parent 指向父节点
  • leftchild 指向左子节点
  • rightchild 指向右子节点

treenode

堆

一个堆最重要的两个方法是：

  • push 增加一个元素到堆尾，并沿着路径上行到合适位置
  • pop 交换堆首尾元素，取出队尾元素，将堆顶元素下行到合适位置

示例

heap

如何根据结点的序号快速的定位结点

在堆的两个方法push pop需要解决如何快速地寻找队尾元素，可以采取如下的方法：
3
如上图，若现在堆大小为4，则插入元素位置应该在5，其二进制101表示其路径为：根节点->左子树->右子树

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
#include <iostream>
#include <list>
using namespace std;

// 整数转二进制
list<int> BinaryVector(int n) {
	int temp;  
	temp=n;  
	list<int> L;  
	while(temp!=0)  
	{  
		L.push_front(temp%2);  
		temp=temp >> 1;  
	}  
	return L;
}

template<class T>
class treenode {
	public:
		treenode() ;
		treenode(T newelem){
			value = newelem;
			parent = leftchild = rightchild = NULL;
		}
		T value;
		treenode *parent, *leftchild, *rightchild;
};

template<class T>
class heap {
	public:
		heap() {
			root = NULL;
			size = 0;
		}
		~heap(){
		}
		bool push(T newelem);
		T pop();
		void recursion_inorder_traversal();
		void recursion_preorder_traversal();
	private:
		int size;
		treenode<T> *root;
		void _recursion_inorder_traversal(treenode<T> *p);
		void _recursion_preorder_traversal(treenode<T> *p);
};


// 中序遍历
template <class T>  
void heap<T>::_recursion_inorder_traversal(treenode<T> *p) {
	if (p==NULL) return;
	_recursion_inorder_traversal(p->leftchild);
	cout << p->value << ' ';
	_recursion_inorder_traversal(p->rightchild);
	return ;
}

template <class T>  
void heap<T>::recursion_inorder_traversal() {
	_recursion_inorder_traversal(root);
}

// 前序遍历
template <class T>  
void heap<T>::_recursion_preorder_traversal(treenode<T> *p) {
	if (p==NULL) return;
	cout << p->value << " ";
	_recursion_preorder_traversal(p->leftchild);
	_recursion_preorder_traversal(p->rightchild);
	return ;
}

template <class T>  
void heap<T>::recursion_preorder_traversal() {
	_recursion_preorder_traversal(root);
}

//  插入
template <class T>  
bool heap<T>::push(T newelem) {
	// 数量+1
	size += 1;
	// 创建一个节点
	treenode<T> *p = new treenode<T>(newelem);

	// 第一个节点为根节点
	if (size == 1) {
		root = p;
		return true;
	}

	// 插入到堆尾
	list<int> L = BinaryVector(size);
	list<int>::iterator iter=L.begin();
	treenode<T> *rec = root;
	for (iter++;iter!=L.end();iter++) {
		// 往左走
		if (*iter == 0) {
			if (rec->leftchild == NULL) {
				rec->leftchild = p;
				p->parent = rec;
				break;
			}
			rec = rec->leftchild;
		}
		// 往右走
		if (*iter == 1) {
			if (rec->rightchild == NULL) {
				rec->rightchild = p;
				p->parent = rec;
				break;
			}
			rec = rec->rightchild;
		}
	}

	// 上行
	while(p->parent != NULL && p->value > p->parent->value) {
		T tmp = p->value;
		p->value = p->parent->value;
		p->parent->value = tmp;
		p = p->parent;
	}
}

// 弹出
template <class T>  
T heap<T>::pop() {
	if(size == 0) {
		T nil;
		return nil;
	}


	T res = root->value;
	if (size == 1) {
		delete root;
		return res;
	}

	// 交换首尾元素并删除尾部
	list<int> L = BinaryVector(size);
	list<int>::iterator iter=L.begin();
	treenode<T> *rec = root;
	for (iter++;iter!=L.end();iter++) {
		// 往左走
		if (*iter == 0) {
			rec = rec->leftchild;
			// 到达了叶子节点
			if(rec->leftchild == NULL && rec->rightchild == NULL)
				rec->parent->leftchild = NULL;
		}
		// 往右走
		if (*iter == 1) {
			rec = rec->rightchild;
			// 到达了叶子节点
			if(rec->leftchild == NULL && rec->rightchild == NULL)
				rec->parent->rightchild = NULL;
		}
	}
	T tmp = rec->value;
	rec->value = root->value;
	root->value = tmp;
	delete rec;

	size -= 1;

	// 顶部元素下行
	L = BinaryVector(size);
	treenode<T> *p = root;
	for (iter=L.begin();iter!=L.end();iter++) {
		if (p->leftchild == NULL && p->rightchild == NULL) break;
		// 找到子树中较大的
		treenode<T> *maxChild;
		if (p->leftchild == NULL) {
			maxChild = p->rightchild;
		} else if (p->rightchild == NULL) {
			maxChild = p->leftchild;
		} else {
			maxChild = (p->leftchild->value > p->rightchild->value) ? p->leftchild : p->rightchild;
		}
		// 比较父节点与子节点中较大者并交换
		if (p->value < maxChild->value) {
			T tmp = p->value;
			p->value = maxChild->value;
			maxChild->value = tmp;
		}
		p = maxChild;
	}
	return res;
}


int main(int argc, char** argv) {

	heap<int> *h = new heap<int>();
	h->push(2);
	h->push(1);
	h->push(3);
	h->push(4);
	cout << "中序遍历" << endl;
	h->recursion_inorder_traversal();
	cout << endl;
	cout << "前序遍历" << endl;
	h->recursion_preorder_traversal();
	cout << endl;
	int a = h->pop();
	cout << endl;
	cout << a << endl;
	a = h->pop();
	cout << a << endl;
	a = h->pop();
	cout << a << endl;
	a = h->pop();
	cout << a << endl;

	return 0;
}

输出结果：
中序遍历
1 3 4 2
前序遍历
4 3 1 2

4
3
2
1

补充：js实现堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 调整堆
function rebuildHeap(arr, root, size) {
  var child = root * 2
  if (child < size) {
    var rightChild = child + 1

    // 找出左右子节点最大的那个
    if (rightChild < size && arr[child] < arr[rightChild]) {
      child = rightChild
    }

    // 如果根节点小于子节点中的最大者，交换他们
    if (arr[root] < arr[child]) {
      var temp = arr[child]
      arr[child] = arr[root]
      arr[root] = temp
      // 继续调整子节点
      rebuildHeap(arr, child, size)
    }
  }
}

function heapSort(arr) {
  var size = arr.length

  // 从下到上调整建堆
  for (var i = size-1; i>=0; i--) {
    rebuildHeap(arr, i, size)
  }

  // 每次循环取出堆顶元素放到当前未排序的尾部
  for (var last = size - 1; last >= 0; ) {
    var temp = arr[0]
    arr[0] = arr[last]
    arr[last] = temp
    rebuildHeap(arr, 0, last--)
  }
  return arr
}