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

月见樽

发布于 2018-04-27 13:59:56

7960

发布于 2018-04-27 13:59:56

文章被收录于专栏：文武兼修ing——机器学习与IC设计文武兼修ing——机器学习与IC设计

应用场景模拟

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

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

应用分析

数据结构

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

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

同时需要具有以下方法：

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

优先堆

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

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

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

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

上移方法

up.png

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

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

下移方法

down.png

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

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

代码实现

数据结构

结构体

通过接口实现一个打印固定字符串的任务，该任务类的执行打印了结构体中包含的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
    }
}

插入方法

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

判断优先堆是否满，若满返回错误
若优先堆不满，调用上移方法将任务插入优先堆，输入的插入位置为next属性标记的位置
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（根节点），输入数据为在位置next-1的数据
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
}

删除方法

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

遍历优先堆，找到该标号的任务，若没找到该任务则返回错误信息
将优先堆中的next-1指向的任务插入待删除任务的位置并调用下移方法维持优先堆限制
返回待删除任务，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")
}

修改优先级方法

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

遍历优先堆，找到该标号任务，若没找到则返回错误信息
修改任务的优先级，并将该任务插入原位置：若优先级提高（优先数降低），调用上移方法；否则调用下移方法。

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2018.03.15 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体分享计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度