算法学习笔记(1)——堆排序

前记:最近回家除了干干所里剩下的活,手头剩了不少时间。于是趁着这个寒假比较长,准备把算法导论看完了。不过隔了很久突然看起,有些生疏,于是准备再实现一遍。选择语言秉承了「人生苦短,我用python」的原则,果断的选择了python。

虽然把代码提交到了github上,不过感觉不能看着书把伪代码翻译一遍就算完了,写完了之后好好感悟一下,记录一下自己的感想也是很重要的,于是准备在博客上大概记录下自己的学习笔记和感想。

所以重点不在于名词定义和原理解释,毕竟wiki上也好,书上也好,都是一翻到处都有。我想记下来的更多的还是自己个人在学习过程中觉得这些算法构思巧妙的地方。

第一天的复习内容是堆排序,我认为巧妙的地方有以下几点。

1.首先这里的堆使用的数据结构是二叉树,在顺序存储二叉树的时候,父节点、左子节点和右子节点的下标之间具有天然的简单倍数、邻近关系。这直接决定了在访问数据时,不需要很大的代价,客观上显著降低了复杂度。

访问各个节点的代码如下所示,为了简便并没有考虑下标越界的异常处理,这也是为了突出原理。用书上的话说就是:

数据抽象、模块化和错误处理等问题往往都被忽略掉了,以便更简练的表达算法的核心内容。

def get_parent(self, index):
	return self.heaplist[index/2+1]

def get_leftchild(self, index):
	return self.heaplist[2*index+1]

def get_rightchild(self, index):
	return self.heaplist[2*index+2]

2.其次,堆排序将一个复杂的工作分成了许多层次,即所谓的分治法(divide-and-conquer)。

逆向思考的话,就是将一个排序问题分解成了「提取最大元素」、「构建最大堆」、「使用两个最大堆一个节点组成一个最大堆」三个层次。

而如果正向思考的话,由于最大堆的最大的节点就是根节点,所以实际问题就变成了「如何将最小的元素都放在叶节点上」、「如何将根节点和某个叶节点交换之后,再次构建最大堆」两步。

虽然实际上使用的方法都是相同的,即从叶节点开始(由于是顺序存储结构,只需要从数组的中间开始倒序进行)构建最大堆,最后自然整个树会变成最大堆;而后将根节点拿出来(《算法导论》中是将根节点放到了数组末尾,由于放到数组末尾之后并不是二叉树的组成部分,其下标与其他节点的下标没有关系,实际就是放到了另一个数组里)。最后自然形成了一定的大小顺序。

从这种角度来看,其实这种排序方法与插排的思想差不多。就是依次为各个元素找到合适的位置,而由于在元素比较多的时候,第一次构建最大堆的时候,所有的元素形成了一定的有序性。所以一般堆排序比插排的效率要高,不过也不是很高,因为受到了算法设计思维(单个、依次操作)的限制。

实现的代码如下所示。

def max_heapify(self, i=0):
	l = 2*i+1
	r = 2*i+2
	if l <= self.length-1 and self.nodelist[l] > self.nodelist[i]:
		largest = l
	else:
		largest = i
	if r <= self.length-1 and self.nodelist[r] > self.nodelist[largest]:
		largest = r
	if largest != i:
		self.nodelist[i], self.nodelist[largest] = self.nodelist[largest], self.nodelist[i]
		self.max_heapify(largest)

def build_max_heap(self):
	for i in reversed(range(0, self.length-2-1)):
		self.max_heapify(i)

def heapsort(self):
	self.build_max_heap()
	for index in reversed(range(1, self.length)):
		self.sortlist.append(self.nodelist[0])
		self.nodelist[index], self.nodelist[0] = self.nodelist[0], self.nodelist[index]
		del self.nodelist[index]
		self.length = len(self.nodelist)
		self.max_heapify()
	self.nodelist = self.heaplist
	self.length = len(self.nodelist)

最终所有的代码在heapsort.py