type TreeNode struct {
      Val int
      Left *TreeNode
      Right *TreeNode
  }

// 通过小顶堆实现，列表里是一个2个数字的列表嵌套
type IHeap []interface{}
// 返回长度
func (h IHeap) Len() int { 
	return len(h) 
}
// 小的值
func (h IHeap) Less(i, j int) bool { 
	return h[i] < h[j] 
}
// 交换
func (h IHeap) Swap(i, j int) { 
	h[i], h[j] = h[j], h[i]
}
// 入堆
func (h *IHeap) Push(x interface{}) {
    *h = append(*h, x)
}
// 出堆，得到最小元素
func (h *IHeap) Pop() interface{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

// 最大堆的定义和实现：
// 最大堆
type maxHeap struct {
	size int
	nums []int
}

// 获取父节点索引
func parent(i int) int {
	if i == 0 {
		return 0
	}
	return (i - 1) / 2
}

// 获取左节点索引
func leftChild(i int) int {
	return 2*i + 1
}

// 右节点索引
func rightChild(i int) int {
	return 2*i + 2
}

// 初始化
func NewMaxHeap() *maxHeap {
	return &maxHeap{}
}

// 获取大小
func (heap *maxHeap) GetSize() int {
	return heap.size
}

// 判断是否为空
func (heap *maxHeap) IsEmpty() bool {
	return heap.size == 0
}

// 插入元素，并向上调整
func (heap *maxHeap) SiftUp(i int) {
	// 小于则赋值
	if heap.size < len(heap.nums) {
		heap.nums[heap.size] = i
	} else { // 大于则扩容
		heap.nums = append(heap.nums, i)
	}
	// 插入的是堆尾，此时的heap.size还没更新，也就是索引
	parI := parent(heap.size)
	childI := heap.size
	// 父节点小于子节点，则交换
	for heap.nums[parI] < heap.nums[childI] {
		heap.nums[parI], heap.nums[childI] = heap.nums[childI], heap.nums[parI]
		childI = parI
		parI = parent(parI)
	}
	heap.size++
}

// 向下调整
func siftDown(heap *maxHeap, parI int) {
	var maxI int
	for {
		leftI := leftChild(parI)
		switch {
		// 左索引超出size
		case leftI+1 > heap.size:
			return

			// 左索引不超,右索引超出size,说明左索引是最后索引
		case leftI+2 > heap.size:
			if heap.nums[parI] < heap.nums[leftI] {
				heap.nums[parI], heap.nums[leftI] = heap.nums[leftI], heap.nums[parI]
			}
			return
		case heap.nums[leftI] >= heap.nums[leftI+1]:
			maxI = leftI
		case heap.nums[leftI] < heap.nums[leftI+1]:
			maxI = leftI + 1
		}

		// 比左右子节点的值都大,返回
		if heap.nums[parI] >= heap.nums[maxI] {
			return
		}

		heap.nums[parI], heap.nums[maxI] = heap.nums[maxI], heap.nums[parI]
		parI = maxI
	}
}

// 取出对中最大元素,即root节点值
func (heap *maxHeap) SiftDown() (int, error) {
	if heap.IsEmpty() {
		return 0, errors.New("maxHeap is empty.")
	}
	vTop := heap.nums[0]
	heap.size--
	heap.nums[0], heap.nums[heap.size] = heap.nums[heap.size], 0

	siftDown(heap, 0)

	return vTop, nil
}


// 查看堆中最大元素
func (heap *maxHeap) GetMax() (int, error) {
	if heap.IsEmpty() {
		return 0, errors.New("maxHeap is empty.")
	}
	return heap.nums[0], nil
}

// A header for a Go map.
type hmap struct {
        // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
        // Make sure this stays in sync with the compiler's definition.
        count     int // # live cells == size of map.  Must be first (used by len() builtin)
        flags     uint8
        B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
        noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
        hash0     uint32 // hash seed

        buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
        oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
        nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

        extra *mapextra // optional fields
}

// A bucket for a Go map.
type bmap struct {
        // tophash generally contains the top byte of the hash value
        // for each key in this bucket. If tophash[0] < minTopHash,
        // tophash[0] is a bucket evacuation state instead.
        tophash [bucketCnt]uint8
        // Followed by bucketCnt keys and then bucketCnt values.
        // NOTE: packing all the keys together and then all the values together makes the
        // code a bit more complicated than alternating key/value/key/value/... but it allows
        // us to eliminate padding which would be needed for, e.g., map[int64]int8.
        // Followed by an overflow pointer.
}

    // 不同类型 key 使用的 hash 算法在编译期确定
	alg := t.key.alg
	// 计算哈希值，并且加入 hash0 引入随机性
	hash := alg.hash(key, uintptr(h.hash0))
	// 比如 B=5，那 m 就是31，二进制是全 1
	// 求 bucket num 时，将 hash 与 m 相与，
	// 达到 bucket num 由 hash 的低 8 位决定的效果
	m := bucketMask(h.B)
	// b 就是 bucket 的地址
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	// oldbuckets 不为 nil，说明发生了扩容
	if c := h.oldbuckets; c != nil {
		// 如果不是同 size 扩容（看后面扩容的内容）
		// 对应条件 1 的解决方案
		if !h.sameSizeGrow() {
			// 新 bucket 数量是老的 2 倍
			m >>= 1
		}
		// 求出 key 在老的 map 中的 bucket 位置
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		// 如果 oldb 没有搬迁到新的 bucket
		// 那就在老的 bucket 中寻找
		if !evacuated(oldb) {
			b = oldb
		}
	}
	// 计算出高 8 位的 hash
	// 相当于右移 56 位，只取高8位
	top := tophash(hash)
	//开始寻找key
	for ; b != nil; b = b.overflow(t) {
		// 遍历 8 个 bucket
		for i := uintptr(0); i < bucketCnt; i++ {
			// tophash 不匹配，继续
			if b.tophash[i] != top {
				continue
			}
			// tophash 匹配，定位到 key 的位置
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			// key 是指针
			if t.indirectkey {
				// 解引用
				k = *((*unsafe.Pointer)(k))
			}
			// 如果 key 相等
			if alg.equal(key, k) {
				// 定位到 value 的位置
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				// value 解引用
				if t.indirectvalue {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	//判断 hmap 是否已经初始化（是否为 nil）
    if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	//...
    //判断是否并发读写 map，若是则抛出异常
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
    //根据 key 的不同类型调用不同的 hash 方法计算得出 hash 值
	alg := t.key.alg
	hash := alg.hash(key, uintptr(h.hash0))
    //设置 flags 标志位，表示有一个 goroutine 正在写入数据。因为 alg.hash 有可能出现 panic 导致异常
	h.flags |= hashWriting
    //判断 buckets 是否为 nil，若是则调用 newobject 根据当前 bucket 大小进行分配
    //初始化时没有初始 buckets，那么它在第一次赋值时就会对 buckets 分配
	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}	
}

//根据低八位计算得到 bucket 的内存地址
	bucket := hash & bucketMask(h.B)
	//判断是否正在扩容，若正在扩容中则先迁移再接着处理
	if h.growing() {
		growWork(t, h, bucket)
	}
	//计算并得到 bucket 的 bmap 指针地址
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
	//计算 key hash 高八位用于查找 Key
	top := tophash(hash)
	var inserti *uint8
	var insertk unsafe.Pointer
	var val unsafe.Pointer
	for {
		//迭代 buckets 中的每一个 bucket（共 8 个）
		for i := uintptr(0); i < bucketCnt; i++ {
			//对比 bucket.tophash 与 top（高八位）是否一致
			if b.tophash[i] != top {
				//若不一致，判断是否为空槽
				if b.tophash[i] == empty && inserti == nil {
					//有两种情况，第一种是没有插入过。第二种是插入后被删除
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					//把该位置标识为可插入 tophash 位置,这里就是第一个可以插入数据的地方
					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				}
				continue
			}
			//若是匹配（也就是原本已经存在），则进行更新。最后跳出并返回 value 的内存地址
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey {
				k = *((*unsafe.Pointer)(k))
			}
			if !alg.equal(key, k) {
				continue
			}
			// already have a mapping for key. Update it.
			if t.needkeyupdate {
				typedmemmove(t.key, k, key)
			}
			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
			goto done
		}
		//判断是否迭代完毕，若是则结束迭代 buckets 并更新当前桶位置
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}
	//若满足三个条件：触发最大 LoadFactor 、存在过多溢出桶 overflow buckets、没有正在进行扩容。就会进行扩容动作（以确保后续的动作）
	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again // Growing the table invalidates everything, so try again
	}