首页 > 其他分享 >加强堆结构说明

加强堆结构说明

时间:2022-11-29 19:57:18浏览次数:66  
标签:index obj get 说明 heap 加强 public indexMap 结构

加强堆结构说明

作者:Grey

原文地址:

博客园:加强堆结构说明

CSDN:加强堆结构说明

关于堆和堆排序的说明

可以参考这篇博客:与堆和堆排序相关的问题

基础的堆结构可以实现数据入堆和出堆以后(即: 调用堆的 pop 和 push 方法),使用O(logN)的时间复杂度可以将堆调整好,如果使用的是 Java 语言,可以用 java.util 包中的 PriorityQueue 实现堆的所有操作。

但是,在实际场景中,有一种情况是:在已知的一个堆中,堆中任意一个元素变换后,也要以O(logN)的时间复杂度把堆结构调整正确。这是 Java 语言自带的堆结构(PriorityQueue)无法做到的,这就引入了「加强堆」的概念。「加强堆」提供如下方法

    public void resign(T obj) {
      
    }

这个方法表示,对于堆中任意的一个元素 obj,如果调整了其对应的数值,整个堆结构还能在时间复杂度O(logN)下调整好。

普通堆结构之所以无法做到,是因为普通的堆结构没有记录任意一个数据所在的位置信息,所以无法从对应的位置进行堆结构调整。所以,「加强堆」结构引入了一个 HashMap

HashMap<T, Integer> indexMap; // 元素在堆中的位置

有了这个HashMap, 就可以很方便得到某个数据项在堆中的位置是什么,在堆的poppush方法中,要把HashMap的逻辑加入

    public void push(T obj) {
      heap.add(obj);
        // obj 这个数据在堆中是什么位置
      indexMap.put(obj, heapSize);
      heapInsert(heapSize++);
    }

    public T pop() {
      T ans = heap.get(0);
      swap(0, heapSize - 1);
      // 要把对应的obj在堆中直接删除
      indexMap.remove(ans);
      heap.remove(--heapSize);
      heapify(0);
      return ans;
    }

更重要的是,在堆的 heapifyheapInsert 操作中,涉及到的堆中两个元素的交换,也要把堆中元素的位置进行交换

// 不要忘记把堆中元素的位置也要做交换!!!!
    private void swap(int i, int j) {
      T o1 = heap.get(i);
      T o2 = heap.get(j);
      heap.set(i, o2);
      heap.set(j, o1);
      indexMap.put(o2, i);
      indexMap.put(o1, j);
    }

以上是铺垫,到了最核心的resign方法,其逻辑如下

    public void resign(T obj) {
      heapInsert(indexMap.get(obj));
      heapify(indexMap.get(obj));
    }

整个过程也非常好理解,就是找到变化的那个数据项的位置,然后执行heapifyheapInsert,由于变换过程无非是变大或者变小,所以找到变换的位置,heapifyheapInsert操作只会执行一个操作!另外一个操作进去以后会直接跳出。

加强堆的完整代码如下(支持泛型):

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class Code_CustomHeap {

  // 自己手写堆
  public static class HeapGreater<T> {

    private ArrayList<T> heap;
    private HashMap<T, Integer> indexMap; // 元素在堆中的位置
    private int heapSize; // 和heap配合使用
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<T> c) {
      heap = new ArrayList<>();
      indexMap = new HashMap<>();
      comp = c;
    }

    public boolean isEmpty() {
      return heapSize == 0;
    }

    public int size() {
      return heapSize;
    }

    public boolean contains(T obj) {
      return indexMap.containsKey(obj);
    }

    public T peek() {
      return heap.get(0);
    }

    public void push(T obj) {
      heap.add(obj);
      indexMap.put(obj, heapSize);
      heapInsert(heapSize++);
    }

    public T pop() {
      T ans = heap.get(0);
      swap(0, heapSize - 1);
      indexMap.remove(ans);
      heap.remove(--heapSize);
      heapify(0);
      return ans;
    }

    public void remove(T obj) {
      T replace = heap.get(heapSize - 1);
      int index = indexMap.get(obj);
      indexMap.remove(obj);
      heap.remove(--heapSize);
      if (obj != replace) { // obj == replace表示删掉的是最后一个位置的数据,此时不需要进行resign操作
        heap.set(index, replace);
        indexMap.put(replace, index);
        resign(replace);
      }
    }

    public void resign(T obj) {
      heapInsert(indexMap.get(obj));
      heapify(indexMap.get(obj));
    }

    // 请返回堆上的所有元素
    public List<T> getAllElements() {
      List<T> ans = new ArrayList<>();
      for (T c : heap) {
        ans.add(c);
      }
      return ans;
    }

    private void heapInsert(int index) {
      while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
        swap(index, (index - 1) / 2);
        index = (index - 1) / 2;
      }
    }

    private void heapify(int index) {
      int left = index * 2 + 1;
      while (left < heapSize) {
        int best =
            left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0
                ? (left + 1)
                : left;
        best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
        if (best == index) {
          break;
        }
        swap(best, index);
        index = best;
        left = index * 2 + 1;
      }
    }

    private void swap(int i, int j) {
      T o1 = heap.get(i);
      T o2 = heap.get(j);
      heap.set(i, o2);
      heap.set(j, o1);
      indexMap.put(o2, i);
      indexMap.put(o1, j);
    }
  }
}

使用加强堆来解决的问题示例,见使用加强堆解决 topK 问题

更多

算法和数据结构笔记

参考资料

算法和数据结构体系班-左程云

标签:index,obj,get,说明,heap,加强,public,indexMap,结构
From: https://www.cnblogs.com/greyzeng/p/16936506.html

相关文章

  • SQL注入问题、视图、触发器、事物、存储过程、函数、流程控制、索引相关概念、索引数
    目录SQL注入问题视图触发器事物存储过程函数流程控制索引相关概念索引数据结构慢查询优化测试装备联合索引全文检索插入数据更新数据删除数据主键外键重命名表事物安全管理......
  • 数据结构(3):栈(下)
    上回说到,栈是只能在某一端进行各种操作的线性表,我们把这一端称之为栈顶,那么另一端就是栈底,其特点为后进先出(LIFO)。这一回,我们来看一下栈的3个常见应用:括号匹配、表达式求......
  • 数据结构(4):队列(下)
    上回说到,队列是一个先进先出的操作受限的线性表。这一回,我们看到队列的两个常见的应用:层次遍历和在计算机系统中的应用。队列在层次遍历中的应用在信息处理中有一大类问题需......
  • 数据结构(5):数组
    上一回简单的说了一下队列两个常见的应用:层次遍历以及在计算机系统中的应用,这一回,我们来看一个大家都非常熟悉的数据结构:数组!数组的定义数组是由n(n≥1)个相同类型的数据元素......
  • SQL注入问题、视图、触发器、事务、存储过程、函数、函数、索引相关概念、索引数据结
    目录SQL注入问题视图触发器事务存储过程函数函数索引相关概念索引数据结构慢查询优化测试索引联合索引全文检索插入数据更新数据删除数据主键外键重命名表事务安全管理隔离......
  • thread常用API说明
    thread常用API说明1.当有很多线程在执行的时候,我们怎么去区分这些线程呢?此时需要使用Thread的常用方法:getName()、setName()、currentThread()等。1、此方法是Thread......
  • C++数据结构和算法:位运算、字符串
    --------------------------------位运算---------------------------------Q1.用位运算交换两个值前提:要交换的两个值是独立内存voidSwap(int&a,int&b){a......
  • XCode 4.2.1 项目的几个模版说明
    XCode4.2.1项目的模版截图: SingleViewApplication Thistemplateprovidesastartingpointforanapplicationthatusesasingleview.Itprovidesaviewcont......
  • JWT 结构
    Jsonwebtoken的结构Header头部+Payload负载+Signature签名1.JWT-headerheader由两部分组成:令牌类型+散列算法JWT头部分是一个描述JWT元数据......
  • redis 配置说明
    #Redis配置文件#当配置中需要配置内存大小时,可以使用1k,5GB,4M等类似的格式,其转换方式如下(不区分大小写)##1k=>1000bytes#1kb=>1024bytes#1m=>1000000......