当前位置: 首页 > news >正文

58同城网站建设推广网站建设中国建设造价工程协会网站

58同城网站建设推广网站建设,中国建设造价工程协会网站,seo产品优化免费软件,重庆顶呱呱网站建设目录 堆 二叉堆的实现 二叉堆的插入 二叉堆取出堆顶 (extract/delete max) 优先对列 (priority queue) 堆的实现 语言中堆的实现 leadcode 题目堆应用 堆 堆是一种高效维护集合中最大或最小元素的数据结构。 大根堆:根节点最大的堆…

目录

二叉堆的实现

二叉堆的插入

二叉堆取出堆顶 (extract/delete max)

优先对列 (priority queue)

堆的实现

语言中堆的实现

leadcode 题目堆应用


堆是一种高效维护集合中最大或最小元素的数据结构。

大根堆:根节点最大的堆,用于维护和查询max。

小根堆:根节点最小的堆,用于维护和查询min

堆是一棵树,并且满足堆特质:大根堆任意节点的关键码 >= 它所有子节点的关键码 (父>=子)。小根堆任意节点的关键码<=它所有子节点的关键码 (父<=子)

二叉堆除了满足堆的性质外,它还必须是一棵完全二叉树

常见的操作时间复杂度

建堆:O(N)、查询最值(get max/min) O(1) 、插入O(logN)、取出最值 (delete max/min) O(logN)

二叉堆的实现

假设第一个元素存储在索引(下标)为1的位置的话,这个节点计作p,那么它的左孩子的索引下标是 p2, 右孩子的索引下标是2p+1,那么p节点的父节点为p/2(下取整)

假设第一个元素存储在索引(下标)为0的位置的话,这个节点计作p,那么它的左孩子的索引下标是 p2+1, 右孩子的索引下标是2p+2,那么p节点的父节点为(p-1/2)(下取整)

根据这个特点我们可以用一维数组存储二叉堆

二叉堆的插入

新元素一律插入到数组heap 的尾部,这个点设置成p,然后向上进行一次调整 (heapify up)

若此时已经到达根,就停止。若满足堆性质 (heap[p]<=heap[p/2]) 停止,否则交换 heap[p] 和 heap[p/2] 令 p=p/2 继续调整

时间复杂度是 O(logN)

二叉堆取出堆顶 (extract/delete max)

把堆顶(heap[1)和 堆尾 (heap[n]) 交换,删除堆尾部 (删除最后一个元素) 然后从根向下进行一个调整(heapify Down) 每次与左右子节点中较大的一个比较,检查堆性质,不满足则交换,注意判定子节点是否存在 那么时间复杂度是O(logN)

优先对列 (priority queue)

二叉堆是优先队列一种简单、常见的实现,但不是最优实现 理论上二叉堆可以支持O(logN) 删除任意元素,只需要 定位该元素在堆中的节点p(可以通过数值与索引之间建立映射得倒) 与堆尾交换,删除堆尾。从p向上、向下各进行一次调整 不过优先队列并没有提供这个方法 在各语言内置的库中,需要支持删除任意元素时,一般使用有序集合等基于平衡二叉搜索树的实现

堆的实现

type heapList []int
​
func (h *heapList) insertVal(val int) {*h = append(*h, val)h.shiftUp(len(*h) - 1)
}
​
func (h *heapList) shiftUp(index int) {for index >= 0 {pInde := index / 2if (*h)[pInde] > (*h)[index] {(*h)[pInde], (*h)[index] = (*h)[index], (*h)[pInde]}index--}
}
​
func (h *heapList) Pop() int {val := (*h)[0](*h)[0] = (*h)[len(*h)-1]*h = (*h)[:len(*h)-1]h.shiftDown(0)h.shiftUp(len(*h) - 1)return val
}
​
func (h *heapList) shiftDown(index int) {hLen := len(*h) - 1for index <= hLen {iL := index*2 + 1if iL+1 <= hLen && (*h)[iL+1] < (*h)[iL] {iL += 1}if iL <= hLen && (*h)[iL] < (*h)[index] {(*h)[iL], (*h)[index] = (*h)[index], (*h)[iL]}index = iL}
}

语言中堆的实现

type li []int
​
func (l li) Len() int {return len(l)
}
​
func (l li) Swap(i, j int) {l[i], l[j] = l[j], l[i]
}
​
func (l li) Less(i, j int) bool {return l[i] > l[j]
}
​
func (l *li) Push(val interface{}) {*l = append(*l, val.(int))
}
​
func (l *li) Pop() interface{} {len_l := len(*l)val := (*l)[len_l-1](*l) = (*l)[:len_l-1]return val
}
​
func main() {var list = &li{}heap.Init(list)heap.Push(list, 1)heap.Push(list, 100)heap.Push(list, 50)heap.Push(list, 150)fmt.Println(heap.Pop(list))fmt.Println(heap.Pop(list))fmt.Println(heap.Pop(list))
}

leadcode 题目堆应用

23. 合并 K 个升序链表

给你一个链表数组,每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中,返回合并后的链表。

示例 1:

输入:lists = [[1,4,5],[1,3,4],[2,6]]
输出:[1,1,2,3,4,4,5,6]
解释:链表数组如下:
[1->4->5,1->3->4,2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
/*** Definition for singly-linked list.* type ListNode struct {*     Val int*     Next *ListNode* }*/type heapList []*ListNode
​func (t *heapList) insertNode(node *ListNode){*t = append(*t,node)t.shiftup(len(*t)-1)}
​func (t *heapList) shiftup(index int){for index>=0{pIndex:=index/2if (*t)[pIndex].Val>(*t)[index].Val{(*t)[pIndex],(*t)[index] = (*t)[index],(*t)[pIndex]}index--}}
​func (t *heapList) Pop() *ListNode{val:=(*t)[0](*t)[0] = (*t)[len(*t)-1]*t = (*t)[:len(*t)-1]t.ShiftDown(0)t.shiftup(len(*t)-1)return val}
​func (t *heapList) ShiftDown(index int){hLen:=len(*t)-1for index<=hLen{Lindex:=2*index+1if Lindex+1<=hLen && (*t)[Lindex].Val>(*t)[Lindex+1].Val{Lindex+=1}if Lindex<=hLen && (*t)[Lindex].Val<(*t)[index].Val{(*t)[Lindex],(*t)[index] = (*t)[index],(*t)[Lindex]}index = Lindex}}
​
func mergeKLists(list []*ListNode) *ListNode {heap:= &heapList{}for _,v:=range list{if v==nil{continue}heap.insertNode(v)}head:=&ListNode{}temp:=headfor len(*heap)>0{node:=heap.Pop()temp.Next = nodetemp = temp.Nextif node.Next!=nil{heap.insertNode(node.Next)}}return head.Next
}

http://www.yayakq.cn/news/505326/

相关文章:

  • 乐清门户网站建设潍坊网站建设联系方式
  • 自己做的网站怎么绑定域名做室内装修的网站
  • h5网站开发案例用php做京东网站页面
  • 新八建设集团有限公司网站开发网站要注意什么问题
  • 电商型网站钓鱼网站盗号下载
  • 自动建设网站系统上海最专业的网站设
  • 南京重庆网站建设c网站开发视频教程
  • 寮步网站建设哪家好网站登录界面html
  • 网站建设私人合同范本绩溪做网站
  • 北京天仪建设工程质量检测所网站山东神华网站建设
  • 臭臭猫网站建设大气家具行业商城类公司网站织梦模板
  • 国外做网站卖东西要什么条件推广 广州网站建设公司
  • 合肥最好的网站建设tcms系统
  • 做箱包哪个网站好蒙阴建设局网站
  • 在线建站平台免费建网站对网站建设的建议
  • 在対网站做可能的来自内部和外部的攻击网富全网营销 有效果吗
  • 企业网站建设 邮箱网页设计作业七步诗
  • 防水自己如何建设网站成都小程序开发公司找哪家
  • 自贡电子商务网站建设wordpress预格式化
  • 招远建网站个人网页制作模板怎么做
  • 网络广告推广方式国外搜索引擎优化
  • 鲁谷做网站的公司佛山网站快速排名提升
  • 网站建设的想法和意见钢材技术支持东莞网站建设
  • wordpress网站打开卡网站首页添加代码
  • 成都市 建设领域信用系统网站还有那个网站可以做兼职呢
  • 个人网站可以做资讯小说类包车哪个网站做的最好
  • 自己做网站要买服务器吗网址二维码生成器
  • 电商网站建设的核心是什么flash制作网站top
  • 系统网站网站建设与推广员岗位职责
  • 免费下载中国移动app福州网站优化公司