调度队列的优先堆实现应用场景模拟应用分析代码实现

应用场景模拟

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

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

应用分析

数据结构

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

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

同时需要具有以下方法:

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

优先堆

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

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

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

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

上移方法

up.png

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

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

下移方法

down.png

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

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

代码实现

数据结构

结构体

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

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
}

构造函数

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

优先堆实现

结构体

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

type WorkFIFO struct {
    heap [17]Work
    next int
    size int
}

该结构体构造函数如下:

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
}

上移方法

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

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)
}

下移方法

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

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)
}
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
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,弹出原根节点位置数据
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
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. 修改任务的优先级,并将该任务插入原位置:若优先级提高(优先数降低),调用上移方法;否则调用下移方法。
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")
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏orientlu

读 《C Traps and Pitfalls》Record

单引号实际代表一个整数 双引号代表指向无名数组的起始字符的指针(字符结尾 0) 使用库函数计算得到的字符串长度不包括结尾的0!

12430
来自专栏梧雨北辰的开发录

Swift学习:泛型

本篇将详细总结介绍Swift泛型的用法; Swift泛型代码让你能够根据自定义的需求,编写出适用于任意类型、灵活可重用的函数及类型。它能让你避免代码的重复,用...

9520
来自专栏五分钟学算法

看完这个你还不会 插入排序 么

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

11630
来自专栏java一日一条

(转)Java正则表达式入门

众所周知,在程序开发中,难免会遇到需要匹配、查找、替换、判断字符串的情况发生,而这些情况有时又比较复杂,如果用纯编码方式解决,往往会浪费程序员的时间及精力。因此...

10810
来自专栏Java架构师学习

为Java程序员金三银四精心挑选的五十道面试题与答案

1、面向对象的特征有哪些方面? 【基础】 答:面向对象的特征主要有以下几个方面: 1)抽象:抽象就是忽略一个主题中与当前目标无关的那些方面,以便更充分地...

37660
来自专栏数据结构与算法

1470 数列处理

个人博客:doubleq.win 1470 数列处理  时间限制: 1 s  空间限制: 1000 KB  题目等级 : 青铜 Bronze 题解 题目描述 D...

28050
来自专栏编程坑太多

Python 字典

13540
来自专栏技术小站

c++(二)

算数运算符:+,-,*,/,%,++,--  进行算数运算时,如果存在溢出,则把溢出的部分拿掉(浮点型的难以预测),如 int i=0xffffffff,j;j...

11710
来自专栏数据结构与算法

1081 线段树练习 2 单点查询及区间修改

1081 线段树练习 2 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 大师 Master 题目描述 Description ...

33590
来自专栏菩提树下的杨过

数据结构与算法C#版笔记--排序(Sort)-上

这里讨论的仅限于内部排序(即全部数据都在内存中,通过CPU运算处理元素排序),而且仅限顺序表排序(即不讨论链表,树状结构等结构的排序) 注:排序后的结果可以从小...

233100

扫码关注云+社区

领取腾讯云代金券