3.11 堆排序

1. 堆排序

heap.md 建堆+删除

2. 特点

• 稳定性：不稳定
• 时间：O（nlogn）
• 空间：O（1）

3. 实现

//O(NlogN)
func HeapSort(data []model.Comparable) {
	length := len(data)
	heapify(data, length)
	//extractMax的翻版
	//这里把最大的放到最后一位（即i），然后调整前面的i-1位
	//处理完之后就升序排列了
	for i := length - 1; i > 0; i-- {
		util.Swap(data, 0, i)
		siftDown(data, 0, i)
	}
}

//O(logN)
func siftDown(data []model.Comparable, parentIndex int, length int) {
	//终止条件为一半，因为从这里开始没有左右孩子
	half := length / 2
	for parentIndex < half {
		leftChildIndex := leftChild(parentIndex)
		rightChildIndex := rightChild(parentIndex)

		//先假设左孩子是最大的
		maxIndex := leftChildIndex
		maxChild := data[maxIndex]
		//如果右孩子存在且右孩子比较大，那么更新maxXXX
		if rightChildIndex < length {
			rightChild := data[rightChildIndex]
			if rightChild.CompareTo(maxChild) > 0 {
				maxChild = rightChild
				maxIndex = rightChildIndex
			}
		}

		parent := data[parentIndex]
		if maxChild.CompareTo(parent) <= 0 {
			break
		}

		//把父亲和较大的孩子交换
		util.Swap(data, parentIndex, maxIndex)
		parentIndex = maxIndex
	}

}

// O(NlogN)
func heapify(data []model.Comparable, length int) {
	//从有子节点的节点开始，下沉维护堆的属性
	for i := length>>1 - 1; i >= 0; i-- {
		siftDown(data, i, length)
	}
}

// 获取左孩子的下标
func leftChild(index int) int {
	return index*2 + 1
}

// 获取右孩子的下标
func rightChild(index int) int {
	return index*2 + 2
}

3.1. 测试

func TestHeapSort(t *testing.T) {
	e0 := model.NewElement(0)
	e1 := model.NewElement(1)
	e2 := model.NewElement(2)
	e3 := model.NewElement(3)
	e4 := model.NewElement(4)

	data := []model.Comparable{e3, e4, e0, e1, e2, e3, e3, e0, e1}
	fmt.Println(data)

	HeapSort(data)
	fmt.Println(data)
}

4. 参考

• 排序算法稳定性_百度百科
• 堆排序 - 维基百科，自由的百科全书