自创查找方式:堆查找(错误+缺陷版)
  • 板块学术版
  • 楼主zhangzhixu000001
  • 当前回复14
  • 已保存回复14
  • 发布时间2024/4/15 19:26
  • 上次更新2024/4/15 21:16:47
查看原帖
自创查找方式:堆查找(错误+缺陷版)
1210321
zhangzhixu000001楼主2024/4/15 19:26

注:该版代码会满江紫,请不要提交到任何一道二分题上

自创堆查找(有缺陷版)

01.思想及起源

如果要在一个区间内查找一个数,我们一般会使用二分。
二分的思想简单,实现容易,时间复杂度也只有O(logN)O(logN),几乎是没有缺点的一个查找方式。
燃鹅,有一种数据结构叫做树...
昨天,我突发奇想,能不能利用堆向下调整的思想,进行查找?
于是,实践开始!

实现方式

我们先弄一棵树,啊不,堆:

      1
    /   \
    2    3
   /  \  /  \
   4  5  6  7

我们假设要查4的位置:
我们先从根节点开始查: 1不行,2与3也不行...
这个时候,我们先往左子树搜;
于是就变成了2 4 5。
再搜一遍,发现:左儿子是4!好了,任务完成。
but
如果要搜7,那就完了:
左子树没有,返回-1(此处默认没找到返回-1),那怎么办?搜右子树!
好在这棵树比较浅,3 6 7,右儿子就是7,因此任务成功完成。
整个堆查找的时间复杂度是不稳定的,最好O(logN)O(logN),最坏O(N)O(N),非常之难用......
本人最近正在寻找解决方案,如果您有思路/疑问,请在帖子的下方留言评论,我会根据您的评论改进堆查找。

Last:heapfind code

int heapfind(int num,int find)
{
  if (num>节点总数) return -1;//越界返回-1
  else if(heap[num]==find) return num;//自己
  else if(heap[num+1]==find) return num+1;//兄弟
  else if(heap[num<<1]==find) return num<<1;//左儿子
  else if(heap[num<<1|1]==find) return num<<1|1;//右儿子
  else{
    return max(heapfind(num<<1,find),heapfind(num<<1|1.find));
  }
2024/4/15 19:26
加载中...