前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >基本2D优先堆基本优先队列二叉堆实现优先队列代码实现

基本2D优先堆基本优先队列二叉堆实现优先队列代码实现

作者头像
月见樽
发布2018-04-27 11:05:12
6440
发布2018-04-27 11:05:12
举报

基本优先队列

考虑一种队列:每次取出的数据是队列中最小的元素。这种队列可用于程序调度,作业分配等领域,这种队列被称为优先队列,核心的方法有:

  • Insert()方法:将数据插入优先队列
  • DeleteMin()方法:将队列中的数据中最小的输出并删除

优先队列可以使用堆这一数据结构实现

二叉堆实现优先队列

二叉堆

二叉堆是除了底层外被完全填满的二叉树,最底层的数据也是从左到右填入(完全二叉树)。因为其填满的特性,可以直接使用数组实现该树型结构:一个位于数组i位置的节点的子节点分别是2*i和2*i+1

优先队列实现

当一个二叉堆实现优先队列时,除了要满足堆的基本特性,还要满足一个特性:对任意一个节点,其值小于其所有的子节点(若有子节点)。则递归的来看,位于根(数组位置0)的节点即为最小的数据。

插入方法

对于堆,每次插入的位置是固定的,若直接将插入元素插入该位置,则优先队列的特性被破坏,因此,需要找到合适的插入位置。操作方法为递归的比较插入位置和插入位置父节点的大小,若满足特性则插入,不满足则交换待插入位置和父节点的数据(将父节点数据写入待插入位置,待插入位置为新的父节点)

2d_heap_insert

删除方法

删除方法有两个功能,第一个功能是将最小的数据弹出,这可以直接返回根节点的值实现;第二个功能是更新新的元素,由于堆少了一个节点,而该节点的位置必须是底层最右侧的节点。因此将该节点数据取出,并插入到跟节点的位置,这样堆的特性被破坏。于是取跟节点为待插入位置,递归的比较待插入节点和子节点的最小节点,获得插入该元素的位置。

2d_heap_delete

代码实现

这段代码写的时候状态比较差,仅供参考

结构体

代码语言:javascript
复制
type nodeData struct {
    num  int
    data int
}

type heap2D struct {
    heap   [17]nodeData
    lenght int
    size   int
}

构造函数

代码语言:javascript
复制
func NewHeap2D() *heap2D {
    newHeap := &heap2D{}
    newHeap.size = 15
    newHeap.lenght = 1
    for i := 0; i < newHeap.size; i++ {
        newHeap.heap[i] = nodeData{}
    }
    return newHeap
}

插入方法

代码语言:javascript
复制
func (h *heap2D) Insert(din nodeData) error {
    if h.lenght > h.size {
        return errors.New("heap full")
    }
    i := 0
    for i = h.lenght; h.heap[i/2].num >= din.num && i != 0; i = i / 2 {
        h.heap[i] = h.heap[i/2]
        // 若插入标记小于父节点标记,则向父节点移动
    }
    h.heap[i] = din //插入
    h.lenght++
    return nil
}

弹出方法

代码语言:javascript
复制
func (h *heap2D) DeleteMin() (nodeData, error) {
    if h.lenght == 0 {
        return nodeData{}, errors.New("heap empty")
    }
    dout := h.heap[1] //取出根节点数据,该数据为优先级最高的节点
    err := h.DownFlow(1, h.heap[h.lenght-1]) //调用下移方法将堆中的最后一个节点从根节点插入
    h.lenght--
    return dout, err
}

下移方法

代码语言:javascript
复制
func (h *heap2D) DownFlow(nodeNum int, insert nodeData) error {
    if nodeNum >= h.lenght {
        return errors.New("errors")
    } else if 2*nodeNum >= h.lenght {
        // 无子节点,直接插入
        h.heap[nodeNum] = insert
        return nil
    } else if insert.num < h.heap[h.findMinSon(nodeNum)].num {
        // 两个子节点均大于待插入数据,直接插入
        h.heap[nodeNum] = insert
        return nil
    }
    // 两个子节点的最小标号小于带插入数据标号,递归该过程
    next := h.findMinSon(nodeNum)
    h.heap[nodeNum] = h.heap[next]
    return h.DownFlow(next, insert)
}

// 该方法用于计算出最小子节点标号
func (h *heap2D) findMinSon(nodeNum int) int {
    if 2*nodeNum+1 >= h.lenght {
        return 2 * nodeNum
    }
    if h.heap[2*nodeNum].num > h.heap[2*nodeNum+1].num {
        return 2*nodeNum + 1
    }
    return 2 * nodeNum
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018.02.28 ,如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 基本优先队列
  • 二叉堆实现优先队列
    • 二叉堆
      • 优先队列实现
        • 插入方法
        • 删除方法
        • 结构体
        • 构造函数
        • 插入方法
        • 弹出方法
        • 下移方法
    • 代码实现
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档