当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

二叉树:堆

发表于: 2012-02-21   作者:dieslrae   来源:转载   浏览:
摘要:     这里说的堆其实是一个完全二叉树,每个节点都不小于自己的子节点,不要跟jvm的堆搞混了.由于是完全二叉树,可以用数组来构建.用数组构建树的规则很简单:     一个节点的父节点下标为: (当前下标 - 1)/2     一个节点的左节点下标为: 当前下标 * 2 + 1   &
    这里说的堆其实是一个完全二叉树,每个节点都不小于自己的子节点,不要跟jvm的堆搞混了.由于是完全二叉树,可以用数组来构建.用数组构建树的规则很简单:
    一个节点的父节点下标为: (当前下标 - 1)/2
    一个节点的左节点下标为: 当前下标 * 2 + 1
    一个节点的右节点下标为: 当前下标 * 2 + 2
   
    用数组来构建时,可以非常方便的访问最后一个最后一个节点,所以,堆比较适合于优先级队列之类的应用.每次新增节点时,总是先插入到数组最后一个空位,再依次跟父节点比对,如果父节点小就交换;每次删除节点时总是删除并返回根,然后将最后一个节点放到根的位置,再依次跟比较大的一个子节点比较,如果比子节点大就交换.

堆代码:
import java.util.ArrayList;
import java.util.List;

public class Heap <K,V>{
    private List<Entity<K,V>> heap;
    
    public Heap(){
        heap = new ArrayList<Entity<K,V>>();
    }
    
    public void put(K key,V value){
        Entity<K,V> e = new Entity<K,V>(key, value);
        heap.add(e);
        Comparable<? super K> k = (Comparable<? super K>)key;
        
        int index = heap.size() - 1;
        int parent = (index - 1) / 2;
        
        while(index != parent && k.compareTo(heap.get(parent).key) > 0){
            heap.set(index, heap.get(parent));
            index = parent;
            
            if(index == 0){
                break;
            }
            
            parent = (index -1) / 2;
        }
        
        heap.set(index, e);
    }
    
    public V pop(){
        Entity<K,V> e = heap.get(0);
        
        if(heap.size() == 1){
            heap.remove(0);
        } else {
            Entity<K, V> top = heap.remove(heap.size() - 1);
            heap.set(0, top);

            int left = 1;
            int right = 2;
            int current = 0;

            while (left < heap.size()) {
                int child;
                Comparable<? super K> k = (Comparable<? super K>) heap.get(left).key;

                if (right < heap.size() && k.compareTo(heap.get(right).key) < 0) {
                    child = right;
                } else {
                    child = left;
                }

                k = (Comparable<? super K>) heap.get(current).key;

                if (k.compareTo(heap.get(child).key) < 0) {
                    heap.set(current, heap.get(child));
                    heap.set(child, top);
                    current = child;
                    left = current * 2 + 1;
                    right = left + 1;
                } else {
                    break;
                }
            }
        }
        
        return e.value;
    }
    
    public int size(){
        return heap.size();
    }
    
    public boolean isEmpty(){
        return heap.isEmpty();
    }
    
    private static final class Entity <K,V>{
        private K key;
        private V value;
        
        public Entity(K key,V value){
            this.key = key;
            this.value = value;
        }
    }
}


二叉树:堆

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
在定义堆之前先了解以下2个概念; 最大树:是指在一棵树中,如果一个结点有儿子结点,其关键字值都
原题:http://acm.zzuli.edu.cn/problem.php?cid=1099&pid=9 【描述】 【输入】 【输出】 Sample In
之前做了这五种树的实现,为了更形象的理解树的效果,特意写了绘制函数,得到下面几个图。 每个树做
4
堆的定义 一些按照重要性或者优先级来组织的对象称为优先队列。 堆是一棵完全二叉树,由数组来实现
5
堆 本文我们重点讨论堆,堆分为最小堆和最大堆两种,由于两者操作操作类似,所以我们只讨论最小堆(
6
在求前K大数中可以用堆来维护,但是很久没碰堆这个东西了,BS下自己。重新复习一下吧。 插入堆的时
二叉树 Binary Tree 二叉树的定义 二叉树是一类非常重要的树形结构,它可以递归地定义如下: 二叉树
二叉树概念总结 1、二叉树的递归定义 二叉树(Binary Tree)是个有限元素的集合,该集合或者为空、或
二叉树:每个结点最多有两个子树的有序树 树和二叉树的2个主要差别:   1. 树中结点的最大度数没
二叉树 Binary Tree 二叉树的定义 二叉树是一类非常重要的树形结构,它可以递归地定义如下: 二叉树
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号