java使用小根堆实现优先级队列的几种方式

写在之前

1.自定义实现采用数组作为内部数据结构

2.内部数组通过grow方法进行扩容，每次只是简单的扩展为原来的2倍

3.集中实现方式的主要区别在于siftDown方法

4.以下给出关键代码，更多详细信息请看附件源码

 

实现方式一(递归实现)

关键代码：

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        int left = left(index);
        int right = right(index);
        if(left > len)
        {
            return;
        }
        int currentMin = left;
        if(right <= len && arr[currentMin] > arr[right])
        {
            currentMin = right;
        }
        if(arr[currentMin] < arr[index])
        {
            swap(arr, currentMin, index);
            siftDown(currentMin);
        }
    }

  

实现方式二(循环实现)

关键代码：

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        while(left(index) <= len)
        {
            int left = left(index);
            int right = right(index);
            if(left > len)
            {
                break;
            }
            int currentMin = left;
            if(right <= len && arr[currentMin] > arr[right])
            {
                currentMin = right;
            }
            if(arr[currentMin] >= arr[index])
            {
                break;
            }
            swap(arr, currentMin, index);
            index = currentMin;
        }
    }

 

实现方式三(直接构建堆)

关键代码：

   @Override
    protected void siftDown(int index)
    {
        int len = totalCount - 1;
        while(left(index) <= len)
        {
            int left = left(index);
            int right = right(index);
            if(left > len)
            {
                break;
            }
            int currentMin = left;
            if(right <= len && arr[currentMin] > arr[right])
            {
                currentMin = right;
            }
            if(arr[currentMin] < arr[index])
            {
                swap(arr, currentMin, index);
            }
            //进入下一个非叶子节点
            index++;
            
        }
    }

 

实现方式四(JDK中的实现)

1.siftUp方法：

protected void siftUp(int k, int x) 
    {
        while (k > 0) 
        {
            int parent = parent(k);
            int e = arr[parent];
            if (x >= e)
                break;
            arr[k] = e;
            k = parent;
        }
        arr[k] = x;
    }

 2.siftDown方法：

   /**
     * 指定index位置的值为x，并为x在堆中找到合适位置
     * @param index
     * @param x
     */
    private void siftDown(int index, int x) 
    {
        int half = totalCount >>> 1;        
        while (index < half) 
        {
            int currentMin = left(index);
            int right = right(index);
            if (right < totalCount && arr[currentMin] > arr[right])
                currentMin = right;
            if (x <= arr[currentMin])
                break;
            //将index位置设置为最小节点值
            arr[index] = arr[currentMin];
            //迭代
            index = currentMin;
        }
        //将最终值放入合适位置
        arr[index] = x;
    }

 

其他的一下关键方法

1.siftUp方法：

   @Override
    protected void siftUp(int index)
    {
        int parent = parent(index);
        while(index > 0 && arr[index] < arr[parent])
        {
            swap(arr, index, parent);
            index = parent;
            parent = parent(index);
        }
    }

 2.add方法：

   @Override
    public boolean add(int ele)
    {
        if(totalCount == arr.length)
        {
            //扩容
            grow();
        }
        
        int i = totalCount;
        arr[i] = ele;
        if(totalCount == 1)
        {
            return true;
        }
        
        //调整元素位置确保为小根堆
        siftUp(i);
        totalCount++;
        return true;
    }

 3.poll方法：

   @Override
    public int poll()
    {
        int result = arr[0];
        arr[0] = arr[--totalCount];
        siftDown(0);
        
        return result;
    }

 5.remove方法：

   @Override
    public int remove(int ele)
    {
        //内部数据为空
        if(totalCount < 1)
        {
            return -1;
        }
        
        //计算元素位置
        int index = indexOf(ele);
        if(index < 0)
        {
            return -1;
        }
        
        return removeAt(index);
    }

 6.removeAt方法：

   @Override
    protected int removeAt(int idx)
    {
        if(idx < 0 || idx >= totalCount)
        {
            return -1;
        }
        int result = arr[idx];
        
        //将删除元素与最后一个元素交换位置
        if(idx != totalCount -1)
        {
            arr[idx] = arr[totalCount - 1];
        }
        //位置交换之后队列长度减一
        totalCount--;
        //如果队列长度大于1，而且删除的元素位置不在队尾则重新调整堆
        if(totalCount > 1 && idx != totalCount)
        {
            siftDown(idx);
        }
        return result;
    }