前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >小顶堆Java实现

小顶堆Java实现

作者头像
囚兔
发布2018-02-08 10:37:49
1.7K0
发布2018-02-08 10:37:49
举报
文章被收录于专栏:IT杂记

参考文章:

漫谈经典排序算法:一、从简单选择排序到堆排序的深度解析 http://blog.csdn.net/touch_2011/article/details/6767673

其中实现了如下功能: 1. 创建一个节点数为nodes的堆; 2. 往堆中put一个int值,替换堆顶的元素,也即堆中最小的值; 3. 对堆进行排序; 4. 获取堆数据数组;调用sort后,获取的就是排序后的数组;

代码如下:

代码语言:javascript
复制
import java.util.Arrays;
import java.util.Random;

public class MinFixHeap {
    
    static enum State {
        INITIALIZED, HEAPED, WAIT_HEAP, SORTED
    }
    
    /** Fix node number */
    private int nodes;
    
    /** Fix length data array */
    private int[] data;
    
    private State state;
    
    public MinFixHeap(int nodes) {
        this.nodes = nodes;
        this.data = new int[nodes];   // Element init value is 0
        state = State.INITIALIZED;
    }
    
    /**
     * Adjust to min heap, i point to root
     * @param i  Root node index, from zero
     */
    public static void minHeap(int[] data, int nodes, int i) {
        // Left child node, right child node, least node
        int leftChild, rightChild, least;
        
        least = leftChild = 2 * i + 1;
        
        if(leftChild >= nodes) {
            // i is leaf node, return
            return;
        }
        
        rightChild = leftChild + 1;
        if(rightChild < nodes && data[rightChild] < data[leftChild]) {
            least = rightChild;
        }
        
        if(data[i] > data[least]) {
            // data[i] and data[least] exchange
            data[i] = data[i] + data[least];
            data[least] = data[i] - data[least];
            data[i] = data[i] - data[least];
            
            minHeap(data, nodes, least);
        }
    }
    
    /**
     * Build data to a min heap
     */
    private void buildHeap() {
        
        if(this.state == State.INITIALIZED 
                || this.state == State.HEAPED) {
            return;
        }
        
        for(int i = this.nodes / 2 - 1; i >= 0; i--) {
            minHeap(this.data, this.nodes, i);
        }
        
        this.state = State.HEAPED;
    }
    
    /**
     * Heap sort
     */
    public void sort() {
        
        if(this.state == State.INITIALIZED 
                || this.state == State.SORTED) {
            return;
        }
        
        for(int i = this.nodes - 1; i >= 1; i--) {
            
            // Exchange data[0] and data[i]
            this.data[0] = this.data[0] + this.data[i];
            this.data[i] = this.data[0] - this.data[i];
            this.data[0] = this.data[0] - this.data[i];
            
            minHeap(this.data, i, 0);
        }
        
        this.state = State.SORTED;
    }
    
    /**
     * Put value to data, and get a top 5
     * @param v
     */
    public void put(int v) {
        
        if(this.state == State.SORTED) {
            buildHeap();
        }
        
        if(v > data[0]) {
            data[0] = v;
            this.state = State.WAIT_HEAP;
            buildHeap();
        }
    }
    
    
    @Override
    public String toString() {
        return Arrays.toString(data);
    }
    
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档