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

月见樽

发布于 2018-04-27 11:05:12

6440

发布于 2018-04-27 11:05:12

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

基本优先队列

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

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

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

二叉堆实现优先队列

二叉堆

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

优先队列实现

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

插入方法

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

2d_heap_insert

删除方法

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

2d_heap_delete

代码实现

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

结构体

type nodeData struct {
    num  int
    data int
}

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

构造函数

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

插入方法

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
}

弹出方法

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
}

下移方法

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 条评论

热度