hello，你好，欢迎来到堆排序！
堆排序是典型的数据结构和算法的结合，首先使用数据结构记录了必要的信息，然后算法通过查找数据结构的信息，来决定算法的下一步该怎么进行。以后我们会遇到很多的数据结构，他们通常会在某些特定的算法中起到一种特殊的作用。了解数据结构的特性，也可以给你设计算法的时候提供必要的模型。从某种意义上说，数据结构是算法的一种补充。从另一种意义上说，数据结构是我们认识世界的一个模型特写。简单的说，算法才是编码的重点，但是构造算法的过程，如果你有某种数据结构作为模型，那么算法的就会很容易构造出来，这是一种相互作用的过程，这种思维方式不同与分治法思想，不过这也是一种重要的思想，而且这种思想，更需要你去训练，了解某种数据结构的使用场景，了解该种数据结构的特性，了解一切和该种数据结构相关的内容，这是一个复杂的训练过程，这也是我学习算法的时候最耗时的过程，这个过程没有捷径，不可能像归并排序，我三句话就能说明白的。
数据结构是也可以对现实世界进行建模的，这也是工作种经常要做的事情，相反算法虽然往往比较复杂，不过都可以固化到算法库里面，你只要学会怎么使用就行了，这也是很多人不愿意学习算法的原因，我想说的是，学习算法的过程，是为了巩固你对数据结构的理解，这才可能是为什么程序员必须学习算法，通过学习算法进一步提高你对数据结构的认识！！！
好了，说了这么多，其实我想向你展现的第一个数据结构“堆”。
为了模拟升序排序，这里我使用“大顶堆”，简单的定义就是，堆是一棵满二叉树，每个堆的左子树和右子树都是堆，大顶堆指的是它的根的值不小于他的所有的孩子的值。（啊，太烦了，为了描述它，我脑细胞又死了一堆，这是我对堆的理解，太绕口了，这是一个多么自然的数据结构，我生生的描述成了一个不能理解的数据结构）
二叉树的实现又多种方式，这里由于是满二叉树，所以采用数组法，所谓的数组法就是采用连续的内存空间来存储堆。（我擦， 又是一套专业术语，有时候我都怀疑人生， 你还能理解吗？）
OK，我们还得继续，这里有个问题，如何构建堆？当你学习某种数据结构的时候，这个问题是我们必须要解决的问题。另外一个问题，堆数据结构有哪些基本的操作？这个问题是我们能够使用该种数据结构进行建模的一个本质问题，如果该种数据结构的操作，或者操作的性能不能满足实际问题的要求，那么该种数据结构就不适合这种实际问题的建模，或者说，如果你强行使用不适合的数据结构对实际问题建模，那么你会遇到一切你想不到的麻烦！！！这里，有种特殊情况，就是，我们可以对数据结构进行变体，这样，让变体的模型适应实际问题，堆数据结构就有个变体，优先级队列，这个以后有时间会更新一篇文章。
堆能提供的操作：
- build构建
- push一个新元素
- top最小的元素
- pop一个最小的元素
如果你熟悉堆这个数据结构，那么你一定会知道，这些基本的堆操作都会涉及到如何保持一个堆的性质，简单的说就是维护堆固有的定义。所以我们必须解决这个问题，否则，堆的操作就无法进行。对于复杂的数据结构，维护该数据结构的性质，是操作数据结构的一个基础，比如平衡树。这些复杂的数据结构的性质的维护代码的多少，从某种意义上也体现了这个数据结构的复杂程度，有些特殊的特性，需要特殊的维护代码，更艰难的是，通常这种代码很少能简单的找到共性，简单的说，你很难通过一个有效的公式就能拼凑这种维护数据结构特性的代码。那么如何提高自己对数据结构性质的理解呢？多多的编码和感悟，这是唯一的有效途径！（没有其他更有效的方法，除非你有这方面的天赋，我等鼠辈只能按部就班）所以，那些熟悉各种算法和数据结构的人，值得你去尊重，因为，虽然很多东西都是浅显易懂的，但是不坚持一点一滴的积累，是很难有质的突破。（我好像说了很多的废话。。。废话比你看我的技术文章跟重要，因为，我不是专门研究技术的。。。嘿嘿！！！）
好了，现在来说说，如何确保一个堆的性质，这里我们提供一个方法heapify。（我也不知道为什么叫这个名字，我英语不好，别笑话）
代码1如下：
def heapify(H, HSize, index):
# H: it's the heap
# HSize: heap's size
# index: the element we have to adjust,
# then the heap can keep the heap properties.
def left_child(index):
return (index << 1) + 1
def right_child(index):
return (index << 1) + 2
l_index = left_child(index)
r_index = right_child(index)
max_index = index
if l_index < HSize and H[max_index] < H[l_index]:
max_index = l_index
if r_index < HSize and H[max_index] < H[r_index]:
max_index = r_index
if max_index == index:
return
H[index], H[max_index] = H[max_index], H[index]
heapify(H, HSize, max_index)
呃，如果你是算法的初学者，那么代码1的内容你可能不能够立即明白，里面有几个技巧，比如left_child和right_child的定义，还有就是这是一个递归调整，直到调整到叶子节点，如果index的初值是0，那么表示从堆的根开始调整，调整的之前，左右子树都是堆。这些技巧，我一开始也不能理解，甚至有段时间我产生了放弃的念头，直到有天我遇到一个真的会写这段代码的人，我才明白，这玩意真的可以自己写，而且不用看书写，哦，对了，初学者都喜欢看着书去敲代码，俗语说，先模仿后学习，不过我的建议是模仿可以，学习也是很重要的。我现在可以很自信的告诉你，这段代码是我的第一反应， 堆的这种保持堆性质的操作，我是烂熟于心，我了解堆的性质，我理解它，我了解如何递归的调整，我了解它，我了解为什么使用数组构建堆的基本形态，我了解它，我的这种了解，不是形式化上的了解，不是背书，而是，如果是我来设计，我也只能这样设计，这就是自然化的过程，我相信，你通过努力也可以达到这种状态，一种很自然的状态，训练是必须的。！！！
废话不多说，如果有了这个基本操作heapify，那么其他的操作就会简单的很多。
从一个简单的数组构建堆，代码2如下：
def heap_build(L):
i = len(L) >> 1
while True:
if i < 0:
break
heapify(L, len(L), i)
i -= 1
return L
top操作，代码3如下:
def heap_top(H):
return H[0] if H else None
pop操作，代码4如下：
def heap_pop(H):
if not H:
return
H[0], H[len(H) - 1] = H[len(H) - 1], H[0]
H.pop()
heapify(H, len(H), 0)
push操作，要复杂一点，但是也是可以理解的，代码5如下：
def heap_push(H, ele):
def parent(index):
return (index - 1) >> 1
H.append(ele)
index = len(H) - 1
# find max parent index
while True:
if index <= 0:
break
if H[parent(index)] >= H[index]:
break
index = parent(index)
有了上述的堆的基本操作，堆排序是所有排序算法中最容易的理解的，从这点可以看出，如果理解某种数据结构，那么和这个数据结构相关的模型算法，也会容易理解的多，所以，我才会关注一个程序员知道多少种数据结构，这个可以从一个侧面看出这个程序员的建模能力。
堆排序算法，代码6如下：
def heap_sort(L):
heap_build(L)
i = len(L) - 1
while True:
if i <= 0:
break
L[0], L[i] = L[i], L[0]
heapify(L, i, 0)
i -= 1
return L
好了，堆排序算法就到这里了，你会发现，堆排序的设计也是很自然的，你可以体会一下heapify在这里作用。再次说明一下，以上的所有代码我都是一气呵成的，所以，有些编码你会觉得有点奇怪，不过通过重构，总可以达到你想要的那种状态。好了，这篇文章就到这里了，有什么不明白的，可以留言，如果我能解释，我一定会回复你的！！！
网友评论