0%

堆

发表于 更新于 分类于

堆问题

什么是堆

  • 对于一个数组, 我们可以看作是一颗完全二叉树
  • 树的根就是数组的第一个元素
  • 对于数组中索引为i的元素, 定义
    1. 左节点的索引为i*2 + 1
    2. 右节点的索引为i*2 + 2
    3. 父节点的索引为(i - 1) / 2
    4. 对于索引溢出时, 代表该节点不存在

大顶堆和小顶堆

  • 大顶堆: 由数组形成的完全二叉树的根节点的值大于左右节点的值
  • 小顶堆: 由数组形成的完全二叉树的跟节点的值小于左右节点的值

优先级队列

  • 通过构建一个基于优先级大小作为比较原则的大顶堆, 来实现优先级队列
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    type IPriorityQueue interface {
    	Add(value int)
    	Top() int
    	Pop() int
    	Size() int
    }

    type PriorityQueue struct {
    	arr []int
    	size int
    	Compare func(left, right int) int
    }

    func New(Com func(left, right int) int) *PriorityQueue {
    	return &PriorityQueue{arr: []int{}, size:0, Compare:Com}
    }

    func (queue *PriorityQueue) Add(value int) {
    	if queue.size == len(queue.arr) {
    		queue.arr = append(queue.arr, value)
    	} else {
    		queue.arr[queue.size] = value
    	}
    	queue.size++
    	index := queue.size - 1
    	for queue.Compare(queue.arr[index], queue.arr[(index - 1) / 2]) > 0 {
    		queue.arr[index], queue.arr[(index - 1) / 2] = queue.arr[(index - 1) / 2], queue.arr[index]
    		index = (index - 1) / 2
    	}
    }

    func (queue *PriorityQueue) Top() int {
    	return queue.arr[0]
    }

    func (queue *PriorityQueue) Pop() int {
    	res := queue.arr[0]
    	queue.arr[0] = queue.arr[queue.size - 1]
    	queue.size--
    	index := 0
    	for index < queue.size {
    		maxIndex := index
    		if index * 2 + 1 < queue.size && queue.Compare(queue.arr[maxIndex], queue.arr[index * 2 + 1]) < 0 {
    			maxIndex = index * 2 + 1
    		}
    		if index * 2 + 2 < queue.size && queue.Compare(queue.arr[maxIndex], queue.arr[index * 2 + 2]) < 0 {
    			maxIndex = index * 2 + 2
    		}
    		if maxIndex == index {
    			break
    		}
    		queue.arr[maxIndex], queue.arr[index] = queue.arr[index], queue.arr[maxIndex]
    		index = maxIndex
    	}
    	return res
    }

    func (queue *PriorityQueue) Size() int {
    	return queue.size
    }

应用例题

  • 问题描述: 给定一个不断输入的数字序列, 获得在任意时刻的中位数
  • 思路:
    1. 构建两个优先级队列, 其中一个优先级按照元素的值大的优先级高记作队A, 另一个优先级按照元素值小的优先级高记作队B构建
    2. 每增加一个元素, 判断, 如果值大于队A的堆顶, 加入队B, 否则加入队A
    3. 如果其中Abs(A.size() - B.size()) > 1, 弹出数量多的队的堆顶, 加入另一个堆
    4. 获得中位数时, 如果两个队数量一样大, 取两个队堆顶的值的平均数, 否则取数量多的队的堆顶
  • 代码(需要使用上面的优先级队列)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    type IMiddleValue interface {
    	AddValue (value int)
    	GetMiddle() int
    }

    type MiddleValue struct {
    	bigQueue *PriorityQueue.PriorityQueue
    	smallQueue *PriorityQueue.PriorityQueue
    }

    func New() *MiddleValue {
    	return &MiddleValue{bigQueue:PriorityQueue.New(func(left, right int) int {
    		return left - right
    	}), smallQueue:PriorityQueue.New(func(left, right int) int {
    		return right - left
    	})}
    }

    func (mv *MiddleValue) AddValue(value int) {
    	if mv.bigQueue.Size() == 0 {
    		mv.bigQueue.Add(value)
    	} else if value > mv.bigQueue.Top() {
    		mv.smallQueue.Add(value)
    		if mv.smallQueue.Size() - mv.bigQueue.Size() > 1 {
    			mv.bigQueue.Add(mv.smallQueue.Pop())
    		}
    	} else {
    		mv.bigQueue.Add(value)
    		if mv.bigQueue.Size() - mv.smallQueue.Size() > 1 {
    			mv.smallQueue.Add(mv.bigQueue.Pop())
    		}
    	}
    }

    func (mv *MiddleValue) GetMiddle() int {
    	if mv.bigQueue.Size() == mv.smallQueue.Size() {
    		return (mv.bigQueue.Top() + mv.smallQueue.Size()) / 2
    	}
    	if mv.bigQueue.Size() > mv.smallQueue.Size() {
    		return mv.bigQueue.Top()
    	} else {
    		return mv.smallQueue.Top()
    	}
    }