python_scraps/heap_sort.py at master · mehmetg/python_scraps · GitHub

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

import heapq
import random

class myHeapContainer(list):
	heap = None
	is_max_heap = None
	def _is_in_order(self, parent, child):
		comp_val = parent > child
		#print comp_val
		if self.is_max_heap:
			return comp_val
		else:
			return (not comp_val)

	def __init__(self, arr = None, is_max = False):
		self.is_max_heap = is_max
		self.heap = arr
		if(arr):
			self._heapify()
		else:
			self.heap = []

	def __len__(self):
		return len(self.heap)
	def  _siftdown(self, root, child):
		parent = (child - 1) >> 1
		while parent >= root:
			if not self._is_in_order(self.heap[parent], self.heap[child]):
				self.heap[child], self.heap[parent] = self.heap[parent], self.heap[child]
				child = parent
				parent = (child - 1) >> 1
			else:
				break
	def _siftup(self, root, length = None):
		c_pos = root * 2 + 1
		if length == None:
			tail = len(self)
		else:
			tail = length

		while c_pos < tail:
			r_pos = c_pos + 1
			if r_pos < tail and self._is_in_order(self.heap[r_pos], self.heap[c_pos]):
				c_pos = r_pos
			if not self._is_in_order(self.heap[root], self.heap[c_pos]):
				self.heap[c_pos], self.heap[root] = self.heap[root], self.heap[c_pos]
				root = c_pos
				c_pos = root * 2 + 1
			else:
				break

	def _heapify(self):
		for parent in xrange(len(self)//2,-1,-1):
			self._siftup(parent)

	def heappush(self, item):
		self.heap.append(item)
		self._siftdown(0, len(self)-1)
	def heappop(self):
		self.heap[0], self.heap[-1] = self.heap[-1], self.heap[0]
		retval = self.heap.pop()
		self._siftup(0)
		return retval
	def heapsort(self, arr, is_max = False):
		self.is_max_heap = is_max
		self.heap = arr
		self._heapify()

		for i in xrange(len(arr), 0, -1):
			self.heap[0], self.heap[i-1] = self.heap[i-1], self.heap[0]
			self._siftup(0, i-1)


def main():
	arr = []
	a = range(10,0,-1)
	arr[:] = a
	random.shuffle(arr)
	print(arr)
	h = myHeapContainer(arr, False)
	print(h.heap)
	sarr = []
	while len(h):
		sarr.append(h.heappop())
	print(sarr)
	arr[:] = a
	h.heapsort(arr)
	print(arr)
	arr[:] = a
	h.heapsort(arr, True)
	print(arr)

	'''
	print("_______")


	arr = range(20,0,-1)
	h = myHeapContainer(None, True)
	for x in arr:
		h.heappush(x)
		heapq.heappush(hq, x)
	print(h.heap)
	print(hq)

	while(len(h)):
		h.heappop()
		heapq.heappop(hq)
		print(h.heap)
		print(hq)
	'''


if __name__ == '__main__':
	main()