堆排序及其相关操作

这里记录下堆的相关操作。

op 1：

'''
	@ data: the heap array
	@ p   : index of parent item 
	@ n   : number of data
	@@ Swap p and it's son items, make p the largest of them
'''
def swapForMaxHeap(data, n, p):
	ls = p << 1 | 1
	rs = ls + 1
	# p has two sons or just left
	if ls < n  or rs < n:
		if rs < n:
			if data[ls] < data[rs]: ls = rs
		if data[p] < data[ls]:
			data[p], data[ls] = data[ls], data[p]
		return ls
	return -1

op 2：

'''
	@ data: the heap array
	@ p   : index of parent item 
	@ n   : number of data
	@@ Swap p and it's son items, make p the smallest of them
'''
def swapForMinHeap(data, n, p):
	ls = p << 1 | 1
	rs = ls + 1

	# p has two sons or just left
	if ls < n  or rs < n:
		if rs < n:
			if data[ls] > data[rs]: ls = rs
		if data[p] > data[ls]:
			data[p], data[ls] = data[ls], data[p]
			return ls
	return -1

op 3：

def Swap(data, n, p, ls = 0):
	
	fun = {}
	fun[0] = swapForMaxHeap
	fun[1] = swapForMinHeap
	return fun[ls](data, n, p)

op 4：

'''
	@ data : the heap array
	@ i    : the start index to be fixUp
	@ n    : the number of data
	@ ls   : if 0, it is a max heap, otherwise, min one

	@@ 
'''
def fixUp(data, i, n, ls = 0):
	if n <= 1: return
	if i <= 0 or i >= n: return

	p = (i - 1) >> 1
	while p >= 0:
		Swap(data, n, p, ls)
		p = (p - 1) >> 1

op 5：

def fixDown( data, i, n, ls = 0):
	if n <= 1: return
	if i < 0 or i >= n: return
	while i <= n - 1:
		index = Swap(data, n, i, ls)
		if index == -1: break
		i = index

op 6：

'''
	@ data: data array that adjust to be heap
	@ n   : number of data
	@ ls  : 0-max heap, 1- min heap
'''
def buildHeap(data, n, ls = 0):
	if n <= 1: return
	for i in xrange( (n >> 1) - 1, -1, -1):
		fixDown(data, i, n, ls)

op 7：

def insert(data, new_x, ls = 0):
	data.append(new_x)
	n = len( data )
	fixUp(data, n - 1, n , ls)

op 8：

def delete(data, n, ls = 0):
	if n <= 0: return
	if n == 1:
		del data[0]
		return
	data[0], data[-1] = data[-1], data[0]
	del data[-1]
	print data
	fixDown(data, 0, n - 1, ls)
	

op 9：

def heapSort(data, n, ls = 0):
	if n <= 1: return
	for i in xrange(n - 1, -1, -1):
		data[i], data[0] = data[0], data[i]
		fixDown(data, 0, i, ls)
	data.reverse()
	print data

堆排序及其相关操作,布布扣,bubuko.com

堆排序及其相关操作

原文：http://blog.csdn.net/shiquxinkong/article/details/37733251