应用场景模拟

考虑优先堆的一种应用场景——按优先级的任务调度队列：每个任务有一个优先级和唯一标号，该调度队列需要具有以下功能：

  • 添加任务：将任务添加进调度队列并按优先级置于对应的位置
  • 执行任务：将优先堆中优先级最高的任务取出（并执行）
  • 删除任务：按标号删除队列中的未执行任务
  • 修改任务优先级：修改指定标号任务的优先级

应用分析

数据结构

对于任务，考虑使用类封装，对于一个任务类需要以下特征：

  • 标号：int型，用于区别任务的标号，每个任务有一个且唯一
  • 优先级：int型，每个任务的优先级，该特征越小则优先级越高

同时需要具有以下方法：

  • 任务执行方法：调用该任务表示执行了该任务
  • 优先级修改方法：调用该任务修改优先级

优先堆

定义了数据结构后，使用2D优先堆实现该优先队列，2D优先堆为完全二叉树，且任意一个节点的值小于其子节点的值。要实现场景中的几种功能，需要以下几种方法：

  • Push：对应添加任务，将任务类插入该优先堆中，调用上移方法。
  • Pop：对应执行任务，取出2D优先堆根节点的任务，调用下移方法。
  • Delete：对应删除任务，按标号取出某一节点的任务并调整堆使其满足2D优先堆的条件，调用下移方法
  • Change：对应修改任务优先级，根据调整的情况调用上移或下移方法。

以上提到了两种另外需要实现的方法：

  • 上移方法：将某一节点向上移动，使其满足2D优先堆的限制
  • 下移方法：将某一节点向下移动，使其满足2D优先堆的限制

上移方法

如图所示为一个上移方法，当某位置要插入一个比原先优先值小的任务时，可以调用上移方法使插入不破坏2d优先堆的性质，该方法的递归概括有以下几步，输入为待插入位置和待插入数据：

  1. 边缘判断：若该节点为根节点，没有父节点，则到边缘，将待插入数据直接插入该位置
  2. 性质判断：若该节点的父节点值小于待插入值，则该位置为待插入位置，插入数据
  3. 递归：若以上均不满足，则该位置不是待插入位置，则将父节点数据插入该位置并递归调用，输入的待插入位置为当前位置的父节点，待插入数据不变

下移方法

如图为一个下移方法的例子，当某位置要插入一个比原先优先值大的任务时，可以调用下移方法使其插入不破坏2d优先堆的性质，该方法的递归概括如下所示，输入为带插入位置和待插入数据：

  1. 边缘判断：若该节点为叶子节点，没有子节点，则到边缘，将待插入数据插入该位置
  2. 性质判断：若该节点的两个子节点的优先值均大于该节点，则该位置为待插入位置，插入数据
  3. 递归：若以上均不满足，则该位置不是待插入位置，则将子节点中优先值小的那个节点数据插入该位置并递归调用，输入的位置为原优先值大的子节点位置，待插入数据不变

代码实现

数据结构

结构体

通过接口实现一个打印固定字符串的任务，该任务类的执行打印了结构体中包含的data字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
type PrintWork struct {
	Index    int
	Priority int
	data     string
}

func (p *PrintWork) Execute() error {
	fmt.Println(p.data)
	return nil
}

func (p *PrintWork) ChangePriority(NewPriority int) {
	p.Priority = NewPriority
}

构造函数

1
2
3
func NewWork(index int, priorty int, data string) *Work {
	return &Work{index, priorty, data}
}

优先堆实现

结构体

该结构体包括一个长度为17的队列，第一个位置不使用，共16个可用的位置；一个指示下一个位置的int型变量next；一个标记堆容量的变量size

1
2
3
4
5
type WorkFIFO struct {
	heap [17]Work
	next int
	size int
}

该结构体构造函数如下：

1
2
3
4
5
6
7
8
9
func NewWorkFIFO() *WorkFIFO {
	temp := &WorkFIFO{}
	for i := 0; i < 17; i++ {
		temp.heap[i] = NewWork(0, 999, "")
	}
	temp.next = 1
	temp.size = 17
	return temp
}

上移方法

上移方法主要用于数据插入和权值修改

1
2
3
4
5
6
7
8
9
10
11
12
13
func (w *WorkFIFO) UpFlow(data *Work, place int) error {
	if place > w.next || place == 0 {
		return errors.New("out of index")
	} else if place == 1 {
		w.heap[1] = data
		return nil
	} else if data.Priority >= w.heap[place/2].Priority {
		w.heap[place] = data
		return nil
	}
	w.heap[place] = w.heap[place/2]
	return w.UpFlow(data, place/2)
}

下移方法

下移方法主要用于数据弹出，删除和权值修改

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (w *WorkFIFO) DownFlow(data *Work, place int) error {
	if place > w.next || place == 0 {
		return errors.New("out of index")
	} else if place*2 >= w.next {
		w.heap[place] = data
		return nil
	} else if data.Priority <= w.heap[w.getMinSon(place)].Priority {
		w.heap[place] = data
		return nil
	}
	nextPlace := w.getMinSon(place)
	w.heap[place] = w.heap[nextPlace]
	return w.DownFlow(data, nextPlace)
}
1
2
3
4
5
6
7
8
9
func (w *WorkFIFO) getMinSon(place int) int {
	if 2*place+1 >= w.next {
		return 2 * place
	} else if w.heap[2*place].Priority > w.heap[2*place+1].Priority {
		return 2*place + 1
	} else {
		return 2 * place
	}
}

插入方法

插入方法将新的任务插入优先队列中，步骤为：

  1. 判断优先堆是否满，若满返回错误
  2. 若优先堆不满，调用上移方法将任务插入优先堆，输入的插入位置为next属性标记的位置
  3. next标记的位置+1
1
2
3
4
5
6
7
8
func (w *WorkFIFO) WorkInsert(data *Work) error {
	if w.next > w.size {
		return errors.New("heap is full")
	}
	err := w.UpFlow(data, w.next)
	w.next++
	return err
}

弹出方法

弹出方法为将优先级最高的任务弹出队列，步骤为：

  1. 优先堆是否空，若空则返回错误
  2. 若优先堆不空，调用下移方法，输入的位置为1（根节点），输入数据为在位置next-1的数据
  3. next标记位置-1，弹出原根节点位置数据
1
2
3
4
5
6
7
8
9
func (w *WorkFIFO) WorkPop() (*Work, error) {
	if w.next <= 1 {
		return nil, errors.New("heap is empty")
	}
	thisWork := w.heap[1]
	w.next--
	err := w.DownFlow(w.heap[w.next], 1)
	return thisWork, err
}

删除方法

删除方法为将指定任务（通过任务标号制定）从队列中删除，步骤为：

  1. 遍历优先堆，找到该标号的任务，若没找到该任务则返回错误信息
  2. 将优先堆中的next-1指向的任务插入待删除任务的位置并调用下移方法维持优先堆限制
  3. 返回待删除任务，next标记-1
1
2
3
4
5
6
7
8
9
10
11
func (w *WorkFIFO) WorkDelete(index int) (*Work, error) {
	for i := 1; i < w.next; i++ {
		if w.heap[i].Index == index {
			temp := w.heap[i]
			err := w.DownFlow(w.heap[w.next-1], i)
			w.next--
			return temp, err
		}
	}
	return nil, errors.New("work undefined")
}

修改优先级方法

修改优先级为修改指定任务（通过任务标号指定）的优先级，步骤为：

  1. 遍历优先堆，找到该标号任务，若没找到则返回错误信息
  2. 修改任务的优先级，并将该任务插入原位置：若优先级提高（优先数降低），调用上移方法；否则调用下移方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
func (w *WorkFIFO) ChangePriority(index int, newPriority int) error {
	for i := 0; i < w.next; i++ {
		if w.heap[i].Index == index {
			if w.heap[i].Priority > newPriority {
				w.heap[i].ChangePriority(newPriority)
				w.UpFlow(w.heap[i], i)
			} else {
				w.heap[i].ChangePriority(newPriority)
				w.DownFlow(w.heap[i], i)
			}
		}
	}
	return errors.New("work undefined")
}