精华内容
下载资源
问答
  • 二叉堆

    2020-11-26 23:08:47
    二叉堆,本质上是一种完全二叉树。只是在完全二叉树地基础上有一些其他地特性 复习完全二叉树定义: 只要最后一个节点之前地所有非叶子节点都存在左孩子和右孩子,且所有叶子节点在同一层次上地二叉树就叫做完全...

    二叉堆,本质上是一种完全二叉树。只是在完全二叉树地基础上有一些其他地特性

    复习完全二叉树定义:

    只要最后一个节点之前地所有非叶子节点都存在左孩子和右孩子,且所有叶子节点在同一层次上地二叉树就叫做完全二叉树。
    

    二叉堆

    最大堆(大顶堆)

    最大堆地任何一个父结点的值。都大于或等于它左孩子或者右孩子地值

    二叉堆的根节点叫做堆顶,最大堆的堆顶是整个堆中的最大元素

    最小堆(小顶堆)

    最大堆地任何一个父结点的值。都小于或等于它左孩子或者右孩子地值

    二叉堆地根节点叫做堆顶,最小堆的堆顶是整个堆中的最小元素

    二叉堆的golang实现

    二叉堆的所有节点都存储在数组中
    

    二叉堆也是一种完全二叉树,存储方式是顺序存储,不会浪费空间

    以最小堆为例:
    包含构建最小堆,添加元素及删除元素

    package main
    
    import "fmt"
    
    type Heap struct {
    	slice  []int
    	length int
    }
    
    // 二叉堆尾节点的上浮操作 O(logn)
    func (m *Heap) upAdjust() {
    	if m.length <= 1 {
    		return //最多一个节点,不用操作
    	}
    	childIndex := m.length - 1          //尾节点索引
    	parentIndex := (childIndex - 1) / 2 //尾节点的父节点索引
    	temp := m.slice[childIndex]
    	for childIndex > 0 && temp < m.slice[parentIndex] {
    		m.slice[childIndex] = m.slice[parentIndex]
    		childIndex = parentIndex
    		parentIndex = (childIndex - 1) / 2
    	}
    	m.slice[childIndex] = temp
    }
    
    
    // 二叉堆节点的下沉操作 O(logn)
    func (m *Heap) downAdjust(parentIndex int) {
    	temp := m.slice[parentIndex]    //保存父节点的值,用于最后的赋值
    	childIndex := 2*parentIndex + 1 //获取左孩子节点索引
    	for childIndex < m.length {     //存在左孩子
    		if childIndex+1 < m.length && m.slice[childIndex+1] < m.slice[childIndex] { //如果右孩子存在且小于左孩子,取右孩子的值。总之是取到最小孩子节点值
    			childIndex += 1
    		}
    		if temp < m.slice[childIndex] {
    			break //父节点小于最小孩子节点值,结束上浮操作
    		} else {
    			//完成一次下沉操作,再开始下一次
    			m.slice[parentIndex] = m.slice[childIndex]
    			parentIndex = childIndex
    			childIndex = 2*parentIndex + 1
    		}
    	}
    	m.slice[parentIndex] = temp
    }
    
    //获取二叉堆节点个数
    func (m *Heap) Length() int {
    	return m.length
    }
    
    //添加节点。如果原来是最小堆,能保持最小堆
    func (m *Heap) add(value int) {
    	m.slice = append(m.slice, value)
    	m.length++
    	m.upAdjust()
    }
    
    //删除头节点
    //如果原来是最小堆,能保持最小堆
    func (m *Heap) delete() {
    	if m.length == 0 {
    		return
    	}
    	m.slice[0] = m.slice[m.length-1] //将头节点替换成尾节点
    	m.slice = m.slice[:m.length-1]   //删除原来的尾节点,相当于删除了头节点
    	m.length--
    	m.downAdjust(0)                  //将头节点执行一次下沉操作,使之保持最小堆
    }
    
    //构建最小堆 O(n)
    func (m *Heap) buildMinHeap() {
    	for i := (len(m.slice) - 2) / 2; i >= 0; i-- {
    		//从最后一个非叶子节点开始,向上依次执行下沉操作
    		m.downAdjust(i)
    	}
    }
    
    //生成一个二叉堆
    func NewHeap(slice []int) Heap {
    	heap := Heap{
    		slice:  slice,
    		length: len(slice),
    	}
    	return heap
    }
    
    func main() {
    	testSlice := []int{6, 4, 8, 3, 2, 9}
    
    	heap := NewHeap(testSlice)
    	fmt.Println(heap.slice) //打印普通二叉堆
    
    	heap.buildMinHeap()     //将普通二叉堆转化成最小堆
    	fmt.Println(heap.slice) //打印最小堆
    
    	heap.add(1)             //添加尾节点
    	fmt.Println(heap.slice) //打印添加元素之后的最小堆
    
    	heap.delete()           //删除头节点
    	fmt.Println(heap.slice) //打印删除元素之后的最小堆
    
    }
    
    

    上面的实现代码需要着重理解与掌握,因为后面还会再用到

    二叉堆是实现优先队列和进行堆排序的基础
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 38,585
精华内容 15,434
关键字:

二叉堆