04-堆、结构体排序.md

[TOC]
# 1 比较器与堆

## 1.1 堆结构

### 1.1.1 完全二叉树结构

> 完全二叉树结构：要么本层是满的，要么先满左边的，以下都是完全二叉树

1. 

```
graph TD
A-->B
A-->C
```

2. 

```
graph TD
A-->B
A-->C
B-->D
B-->E
C-->F
```


### 1.1.2 数组实现堆

- 堆结构就是用数组实现的完全二叉树结构


> 用数组实现完全二叉树结构，从数组下标0开始，当成依次补齐二叉树结构的数据

```
graph TD
0--> 1
0--> 2
1--> 3
1-->4
2-->5
2-->6
```

某位置i的左孩子下标为：
```math
lchild = 2*i + 1
```
某位置i的右孩子的下标为：
```math
rchild = 2*i + 2
```
某位置i的父节点位置为：
```math
parent = (i-1) / 2
```

> 当我们不使用数组的0下标，从1位置开始构建完全二叉树时，方便使用位操作：

某位置i的左孩子下标为：
```math
lchild = 2*i <==> i << 1
```
某位置i的右孩子的下标为：
```math
rchild = 2*i + 1 <==> (i << 1) | 1
```
某位置i的父节点位置为：
```math
parent = i / 2 <==> i >> 1
```
### 1.1.3 大根堆与小根堆

- 完全二叉树中如果每棵子树的最大值都在顶部就是大根堆

- 完全二叉树中如果每颗子树的最小值都在顶部就是小根堆

**我们认为堆就是大根堆或者小根堆，既不是大根堆也不是小根堆的完全二叉树只是完全二叉树，不能称之为堆**



### 1.1.4 构建堆

- 堆结构的heapInsert与heapify操作

1、heapInsert

思路：例如我们要构建一个大根堆，我们把所有的数依次添加到一个数组（下标从0开始）中去，每次添加一个数的时候，要去用找父亲节点的公式parent = (i-1) / 2找到父节点区比较，如果比父节点大就和父节点交换向上移动，移动后再用自己当前位置和父亲节点比较...，小于等于父节点不做处理。这样用户每加一个数，我们都能保证该结构是大根堆，对应代码的push方法

> 我们的调整代价实际上就是这颗树的高度层数，logN

2、heapify

> 原堆结构，删除最大值，继续调整维持成大根堆

思路：我们删除了最大值，也就是arr[0]位置，之后我们把堆最末尾的位置调整到arr[0]位置，堆大小减一。让现在arr[0]位置的数找左右孩子比较...，进行hearify操作，让其沉下去。沉到合适的位置之后，仍然是大根堆。对应代码的pop方法

> heapify的下沉操作，仍然是树的高度，logN。堆结构很重要

```Go
package main

import (
	"errors"
)

type Heap interface {
	IsEmpty() bool
	IsFull() bool
	Push(value int) error
	Pop() int
}

func assertListImplementation() {
	var _ Heap = (*MaxHeap)(nil)
}

type MaxHeap struct {
	// 大根堆的底层数组结构
	heap []int
	// 分配给堆的空间限制
	limit int
	// 表示目前这个堆收集了多少个数，即堆大小。也表示添加的下一个数应该放在哪个位置
	heapSize int
}

// NewMaxHeap 初始化一个大根堆结构
func NewMaxHeap(limit int) *MaxHeap {
	maxHeap := &MaxHeap{
		heap:     make([]int, 0),
		limit:    limit,
		heapSize: 0,
	}
	return maxHeap
}

func (h *MaxHeap) IsEmpty() bool {
	return len(h.heap) == 0
}

func (h *MaxHeap) IsFull() bool {
	return h.heapSize == h.limit
}

func (h *MaxHeap) Push(value int) error {
	if h.heapSize == h.limit {
		return errors.New("heap is full")
	}

	h.heap[h.heapSize] = value
	// heapSize的位置保存当前value
	heapInsert(h.heap, h.heapSize)
	h.heapSize++
	return nil
}

// Pop 返回堆中的最大值，并且在大根堆中，把最大值删掉。弹出后依然保持大根堆的结构
func (h *MaxHeap) Pop() int {
	tmp := h.heap[0]
	h.heapSize--
	swap(h.heap, 0, h.heapSize)
	heapify(h.heap, 0, h.heapSize)
	return tmp
}

// 往堆上添加数，需要从当前位置找父节点比较
func heapInsert(arr []int, index int) {
	for arr[index] > arr[(index-1)/2] {
		swap(arr, index, (index-1)/2)
		index = (index - 1) / 2
	}
}

// 从index位置，不断的与左右孩子比较，下沉。下沉终止条件为：1. 左右孩子都不大于当前值 2. 没有左右孩子了
func heapify(arr []int, index int, heapSize int) {
	// 左孩子的位置
	left := index*2 + 1
	// 左孩子越界，右孩子一定越界。退出循环的条件是：2. 没有左右孩子了
	for left < heapSize {
		var largestIdx int
		rigth := left + 1
		// 存在右孩子，且右孩子的值比左孩子大，选择右孩子的位置
		if rigth < heapSize && arr[rigth] > arr[left] {
			largestIdx = rigth
		} else {
			largestIdx = left
		}

		// 1. 左右孩子的最大值都不大于当前值，终止寻找。无需继续下沉
		if arr[largestIdx] <= arr[index] {
			break
		}
		// 左右孩子的最大值大于当前值
		swap(arr, largestIdx, index)
		// 当前位置移动到交换后的位置，继续寻找
		index = largestIdx
		// 移动后左孩子理论上的位置，下一次循环判断越界情况
		left = index*2 + 1
	}
}

// swap 交换数组中的两个位置的数
func swap(arr []int, i, j int) {
	tmp := arr[i]
	arr[i] = arr[j]
	arr[j] = tmp
}
```

### 1.1.5 堆排序

1. 对于用户给的所有数据，我们先让其构建成为大根堆
2. 对于0到N-1位置的数，我们依次让N-1位置的数和0位置的数（全局最大值）交换,此时全局最大值来到了数组最大位置，堆大小减一，再heapify调整成大根堆。再用N-2位置的数和调整后的0位置的数交换，相同操作。直至0位置和0位置交换。每次heapify为logN，交换调整了N次
3. 所以堆排序的时间复杂度为O(NlogN)
4. 堆排序额为空间复杂度为O(1)，且不存在递归行为

```Go
package main

// HeapSort 堆排序额外空间复杂度O(1)
func HeapSort(arr []int) {
	if len(arr) < 2 {
		return
	}

	// 原始版本, 调整arr满足大根堆结构。O(N*logN)
	//for i := 0; i < len(arr); i++ { // O(N)
	//	heapInsert(arr, i) // O(logN)
	//}

	// 优化版本：heapInsert改为heapify。从末尾开始看是否需要heapify=》O(N)复杂度。
	// 但是这只是优化了原有都是构建堆（O(NlogN)），最终的堆排序仍然是O(NlogN)。比原始版本降低了常数项
	for i := len(arr) - 1; i >= 0; i-- {
		heapify(arr, i, len(arr))
	}

	// 实例化一个大根堆,此时arr已经是调整后满足大根堆结构的arr
	mh := MaxHeap{
		heap:     arr,
		limit:    len(arr),
		heapSize: len(arr),
	}

	mh.heapSize --
	swap(arr, 0, mh.heapSize)
	// O(N*logN)
	for mh.heapSize > 0 { // O(N)
		heapify(arr, 0, mh.heapSize) // O(logN)
		mh.heapSize--
		swap(arr, 0, mh.heapSize) // O(1)
	}

}
```

> 关于上述heapInsert改为heapIfy的优化：

在我们从0到N-1进行heapInsert的时候，是O(NlogN),很容易理解。当我们从N-1到0上依次heapify的时候，整体来看，整棵树的根节点的heapify层数N/2，第二层为N/4且有两个节点。那么实质是N个不同的层数相加：

```math
T(N) = (\frac{N}{2} * 1) + (\frac{N}{4} * 2) + (\frac{N}{8} * 3) + (\frac{N}{16} * 4) + ... 

=>

2T(N) = (\frac{N}{2} * 2) + (\frac{N}{2} * 2) + (\frac{N}{4} * 3) + (\frac{N}{8} * 4) + ... 

=>

T(N) = N + \frac{N}{2} + \frac{N}{4} + \frac{N}{8} + ...

=> O(N)

```

**同理，可以按同样方式实现一个小根堆**

**在有些语言中，已经实现了堆，例如Java的优先级队列java.util.PriorityQueue，Golang中的container/heap**

### 1.1.6 语言、系统提供的堆和手写堆的选择

#### 1.1.6.1 系统堆和手写堆选择

> 使用系统提供的堆：如果我们只是要依次拿最大值，那么做成大根堆，如果我们要最小值我们把堆结构做成小根堆。就是简单的我们添加值，拿值，我们就选择系统提供的堆

> 选择手写堆：如果已经放到系统堆中的元素，加入我们根据需求会在放入堆之后要改动这些元素的值，系统堆并不保证弹出来的东西是正确的，这个时候需要我们手动写一个我们自定义的堆。虽然存在那种排好堆改某些元素让其重新有序的堆结构，但是实质上它是重新扫每个元素去heapinsert，代价太高。手动改写堆的例子例如Dijkstra算法就存在改写堆的优化

## 1.2 比较器

1、比较器的实质就是重载比较运算符

2、比较器可以很好的应用在特殊标准的排序上

3、比较器可以很好的应用在根据特殊标准排序的结构上

> 任何有序结构，我们可以传入我们的比较器，自定义我们自己的排序规则，不传它会按自己默认的规则排序

### 1.2.1 Golang中自定义比较行为

> 在Golang中如果需要自定义比较规则，只需要实现sort/srot.go中的Interface接口的Len、Less、Swap三个方法即可

```Go
package main

import (
	"fmt"
	"sort"
)

// Comparator
//    negative , if a < b
//    zero     , if a == b
//    positive , if a > b
type Comparator func(a, b interface{}) int

// 定义可排序的结构
type sortable struct {
	values []interface{}
	// 该结构携带一个自定义的排序策略
	comparator Comparator
}

// Sort 使用Go原生的排序进行包装，该排序在数据规模大的时候使用快排，数据规模小的时候使用插入排序
func Sort(values []interface{}, comparator Comparator) {
	sort.Sort(sortable{values, comparator})
}

func (s sortable) Len() int {
	return len(s.values)
}

func (s sortable) Swap(i, j int) {
	s.values[i], s.values[j] = s.values[j], s.values[i]
}

func (s sortable) Less(i, j int) bool {
	return s.comparator(s.values[i], s.values[j]) < 0
}

// IntComparator 是自定义的整形排序策略，可以实现其他自定义排序策略
func IntComparator(a, b interface{}) int {
	aAsserted := a.(int)
	bAsserted := b.(int)
	switch {
	case aAsserted > bAsserted:
		return 1
	case aAsserted < bAsserted:
		return -1
	default:
		return 0
	}
}

func main() {
	tests := [][]interface{}{
		{1, 1, 0},
		{1, 2, -1},
		{2, 1, 1},
		{11, 22, -1},
		{0, 0, 0},
		{1, 0, 1},
		{0, 1, -1},
	}
	for _, test := range tests {
		Sort(test, IntComparator)
		fmt.Println(test)
	}
}
```