排序>>选择排序>>堆排序

List:

0.概念+伪代码+示例分析
1.堆排序实现
2.Question
  1. start

基本概念:

维基百科http://zh.wikipedia.org/zh-cn/%E5%A0%86%E7%A9%8D%E6%8E%92%E5%BA%8F

function heapSort(A : list[1..n]) {
    max_heap = make_max_heap(A)  #构建一个最大堆
    i = 1
    while(max_heap.size() > 0){   #当堆中还存在值
        A[n-i] = max_heap.pop_max()   #取出最大一个
        i++
    }
}

堆为一棵完全二叉树,每个节点值都>=子节点值

堆排序根据这个特性,首先将所有元素建立堆,然后一个个取出,即有序的

堆中每个节点的位置:

父节点i的左子节点在位置 (2*i);
父节点i的右子节点在位置 (2*i+1);
子节点i的父节点在位置 floor(i/2);

最大堆主要操作逻辑:

插入:将新元素加入完全二叉树最后一个节点,依次往上,调整直到满足父节点值都>=子节点值

删除:移除根节点,将最后一个节点拿到根节点,依次往下,调整

原始:

heap1

插入操作:12,先假定放在最后一个位置,然后从这个节点开始往上,同父节点比较,依次调整

heap2

删除:取走11,将最后一个元素8移到根节点,从上往下,重新调整

heap3

  1. start

根据公式,我们可以使用数组模拟实现完全二叉树(不使用首个位置)

首先,我们先实现堆:

#!/usr/bin/python
# -*- coding:utf-8 -*-
#堆排序
#@author: wklken@yeah.net

#先实现一个最大堆
class MaxHeap:
    def __init__(self):
        self.heap = [0]  #第一个元素用不到,只是为了将下标转为1开始,方便计算节点的位置
    def isEmpty(self):
        return len(self.heap) == 1
    def size(self):
        return len(self.heap) - 1
    #插入节点
    def insert(self, value):
        i = len(self.heap)
        self.heap.append(value)
        while i != 1 and value > self.heap[i/2]:  #如果插入节点大于其父节点,需要交换二者,反复,直到值小于父节点
            self.heap[i], self.heap[i/2] = self.heap[i/2], self.heap[i]  #父节点下移
            i = i/2
        self.heap[i] = value  #把 value插入对应位置
    #删除最大节点——最大的是根节点
    def deleteMax(self):
        if self.isEmpty(): #没有元素了
            return None
        x = self.heap[1]  #最大

        last = self.heap.pop()
        if self.size() == 0: #每次取最后一个,若是只剩两个的情况,pop
            return x
        #每次,移除根节点,将树的最后一个节点挪到根节点,然后从上到下,调整位置,保证树是一个最大堆
        i = 1
        ci = 2
        current_size = self.size()
        while  ci <= current_size:
            if ci < current_size and self.heap[ci] < self.heap[ci+1]:
                ci += 1

            if last >= self.heap[ci]:
                break

            self.heap[i] = self.heap[ci]
            i = ci
            ci *= 2
        self.heap[i] = last
        return x

    def initFromList(self, l):
        self.heap.extend(l)
        size = self.size()
        #从最后一棵子树开始,调整每一棵子树
        for i in range(size/2,0,-1):
              t_root = self.heap[i]

              c = 2*i
              while c <= size:
                  if c < size and self.heap[c] < self.heap[c+1]:
                      c += 1
                  if t_root >= self.heap[c]:
                      break
                  self.heap[c/2] = self.heap[c]
                  c *= 2
                  self.heap[c/2] = t_root

然后,实现排序过程:

def heap_sort(l):
    m = MaxHeap()
    m.initFromList(l)
    result = []
    for i in range(len(l)):
        result.append(m.deleteMax())
        print result
    return result
  1. start

A.概念,过程描述?

B. 时间复杂度?空间复杂度?是否是稳定排序?

C.适用场景,何种情况下表现最优