heap data structure

yidao620c · yidao620c · commit dc6646720d88 · 2013-09-25T16:44:10.000+08:00
diff --git a/ch01_basic/at003_insertsort.py b/ch01_basic/at003_insertsort.py
@@ -4,6 +4,10 @@
 """
     Topic: sample
     Desc : 插入排序
+        由于其内层循环非常紧凑，对于小规模的输入，
+        插入排序是一种非常快的原址排序算法
+        注： 如果输入数组中仅有常数个元素需要在排序过程中存储在数组外，
+            则称这种排序算法是原址的。
 """
 __author__ = 'Xiong Neng'
 
diff --git a/ch01_basic/at012_codefunny.py b/ch01_basic/at012_codefunny.py
@@ -0,0 +1,20 @@
+#!/usr/bin/env python
+# -*- encoding: utf-8 -*-
+# at012: 编程之美的几个小算法
+"""
+    Topic: sample
+    Desc : 编程之美的几个小算法
+"""
+__author__ = 'Xiong Neng'
+
+
+def listChess():
+    """
+    打印连个将/帅的所有合法的位置，
+    用1..9标明第一个将9个位置，1..9标明第二个帅
+    """
+    for i in range(1, 10):
+        print([(i, k) for k in range(1, 10) if abs(k - i) % 3 != 0])
+
+if __name__ == '__main__':
+    listChess()
diff --git a/ch01_basic/at013_randpermute.py b/ch01_basic/at013_randpermute.py
@@ -0,0 +1,52 @@
+#!/usr/bin/env python
+# -*- encoding: utf-8 -*-
+# at013_randpermute: 随机排列数组算法
+"""
+    Topic: sample
+    Desc : 随机排列数组算法
+        第一种算法：
+        对给定的数组A，我们对每个A[i]生成一个随机的优先级
+        然后根据这个优先级对A进行排序，这个排序需要O(nlg(n))复杂度
+        第二种算法：
+        原址排列给定数组，在O(n)时间内完成，在进行第i次迭代时，
+        A[i]从A[i]至A[n]中随机选取。之后A[i]就再也不变了。
+"""
+from random import randint, shuffle
+
+__author__ = 'Xiong Neng'
+
+
+def randPermuteBySort(seq):
+    """
+    对给定的数组A，我们对每个A[i]生成一个随机的优先级
+    然后根据这个优先级对A进行排序，这个排序需要O(nlg(n))复杂度
+    """
+    maxR = pow(len(seq), 3)
+    p = []
+    for i in range(0, len(seq)):
+        p.append(randint(1, maxR))
+    seq[:] = [m for (m, n) in sorted(zip(seq, p), key=lambda k: k[1])]
+
+
+def randPermuteBySwap(seq):
+    """
+    原址排列给定数组，在O(n)时间内完成，在进行第i次迭代时，
+    A[i]从A[i]至A[n]中随机选取。之后A[i]就再也不变了。
+    """
+    le = len(seq)
+    for i in range(0, le):
+        swapIndex = randint(i, le - 1)
+        seq[i], seq[swapIndex] = seq[swapIndex], seq[i]
+
+
+if __name__ == '__main__':
+    se = [4, 5, 12, 44, 56, 6]
+    randPermuteBySort(se)
+    print(se)
+    se = [4, 5, 12, 44, 56, 6]
+    randPermuteBySwap(se)
+    print(se)
+    se = [4, 5, 12, 44, 56, 6]
+    shuffle(se)  # python中的函数
+    print(se)
+
diff --git a/ch02_sort/__init__.py b/ch02_sort/__init__.py
@@ -0,0 +1,7 @@
+#!/usr/bin/env python
+# -*- encoding: utf-8 -*-
+"""
+    Topic: sample
+    Desc : 排序和顺序统计量
+"""
+__author__ = 'Xiong Neng'
diff --git a/ch02_sort/at014_heapsort.py b/ch02_sort/at014_heapsort.py
@@ -0,0 +1,73 @@
+#!/usr/bin/env python
+# -*- encoding: utf-8 -*-
+# at014_heapsort: 堆排序
+"""
+    Topic: sample
+    Desc : 堆排序
+        堆排序的时间复杂度是O(nlg(n))，并且具有空间原址性
+        二叉堆heap是一种数据结构，可用来实现优先队列
+        给定一个节点的下标i(下标从0开始)，则其父节点、坐孩子、右孩子坐标：
+        parent(i) = floor((i+1)/2 - 1) = ((i + 1) >> 1) - 1
+        left(i) = 2*i + 1 = (i << 1) + 1
+        right(i) = 2*i + 2 = (i + 1) << 1
+
+        最小堆定义： 所有i必须满足A[parent(i)] <= A[i]
+        最大堆定义： 所有i必须满足A[parent(i)] >= A[i]
+
+        在堆排序中，我们使用最大堆
+        在优先队列算法中，使用最小堆
+"""
+__author__ = 'Xiong Neng'
+
+
+def heapSort(heap):
+    """
+    堆排序算法
+    """
+    __buildMaxHeap(heap)
+    for i in range(heap[2] - 1, 0, -1):
+        heap[0][0], heap[0][i] = heap[0][i], heap[0][0]
+        heap[1] -= 1
+        __maxHeapify(heap, 0)
+
+
+def __maxHeapify(heap, i):
+    """
+    前提是i的两棵子树left(i)和right(i)的二叉树都是最大堆了
+    现在加入i节点后，要保持这个二叉树为最大堆的性质
+    heap: 一个包含[seq，heapSize，length]的数组
+    """
+    seq = heap[0]
+    slen = heap[1]
+    while True:
+        left = (i << 1) + 1
+        right = (i + 1) << 1
+        if left < slen and seq[left] > seq[i]:
+            largest = left
+        else:
+            largest = i
+        if right < slen and seq[right] > seq[largest]:
+            largest = right
+        if largest != i:
+            seq[largest], seq[i] = seq[i], seq[largest]
+            i = largest
+        else:
+            break
+
+
+def __buildMaxHeap(heap):
+    """
+    由完全二叉树的性质可知：对于 n/2..n-1为下标的元素，都是叶子节点，
+    那么可从下标floor((i+1)/2 - 1)开始往前到0的元素调用maxHeapify
+    heap: 一个包含[seq，heapSize，length]的数组
+    """
+    slen = heap[1] = heap[2]
+    for i in range(((slen + 1) >> 1) - 1, -1, -1):
+        __maxHeapify(heap, i)
+
+
+if __name__ == '__main__':
+    h = [[9, 7, 8, 10, 16, 3, 14, 2, 1, 4], 0, 10]
+    heapSort(h)
+    print(h[0])
+
