二项堆在二级市场交易软件设计中的运用
【摘要】本文叙述了如何基于二项堆构建二级市场交易平台，以及该数据结构在本平台中的优越性，同时给出了一个平台实现的实例。
【关键词】二项堆 二级市场 证券研究
一、二级市场交易平台简介及其数学模型
二级市场是指对已经发行的证券进行买卖，转让和流通的市场，若抽象为数学模型，则是这样的一个模型：设有两个有限集合 B 和 S，分别表示由买方和卖方的价格构成的集合。交易时，需要每次选择 B 中最大的一个数（愿意出最高价格购买的），选择 S 中最小的一个数（愿意出最低价格出售的），「撮合」两者进行交易。
设计一个具有这样功能的程序时，不难发现，最重要的问题是选择这样一个数据结构：第一，能以非常高的效率从集合中选出最大（最小）的数字；第二，能在交易（即选出最大或最小数字做运算）的同时，将新的挂单「插入」这个数据结构，并不影响正常的交易进行。
二、选择二项堆的原因分析
若我们需要在一堆数字中迅速找到极值，则堆是一种非常好的数据结构，因为找出极值需要的复杂度仅为 O（1），删除为 O（logn），非常高效。
但是，如何能在交易（即选出最大或最小数字做运算）的同时，将新的挂单「插入」这个数据结构，并不影响正常的交易进行？
一种直观的想法是：程序具有两个线程，他们都可以访问 B 堆和 S 堆。其中一个线程负责从两堆中取出极值进行交易，另外一个线程则负责把新的挂单「插入」B 堆和 S 堆。但这样程序的效率是非常底下的，原因如下：第一，堆的「插入」操作复杂度为 O（logn），若当 B 堆（或 S 堆）中的待处理挂单特别多，即 n 特别大时，插入一个新挂单的复杂度是相当大的，这就影响了程序运行的速度；第二：在插入的过程中，由于堆的性质被破坏了，所以在插入的过程中，交易是应该停止的。
所以我们产生了第二个想法：假如场内的买单都在 B 堆中，卖单都在 S 堆中，买单的缓冲区为 B』堆，卖单的缓冲区为 S』堆。在正常交易时，B 堆和 S 堆进行交易操作，B』堆和 S』堆接收新增的挂单。在一定延迟时间后（如 0.2 秒），我们将 B 堆和 B』堆，S 和 S』堆进行「合并」操作，这样就可以保证，每个挂单在 0.2 秒内都可以进入场内。并且，B 堆和 S 堆就有更多的时间用于交易运算了。
对于堆来说，进行「合并」操作的复杂度是 O（n），然而，有一种名为「二项堆」的数据结构，在保持堆的性质的同时，「合并」操作的复杂度仅为 O（lgn）。这样在每秒内，程序仅需极短时间并入缓冲区，场内就有更多的时间进行交易运算，达到更高的效率。
三、交易平台程序的总体结构设计和分析
基于二项堆 ，我们可以设计出如下的交易平台程序总体结构：
四、程序测试
按照本结构就可以设计出一个简单的交易平台软件。笔者使用 Java 语言实现了一个交易平台，并编写了具有 AI 的客户端。AI 的行为模式如下：
股票交易的一个周期定义为 1 秒；
AI 作为买方（卖方）交易时，将会询问市场上的最低卖价（最高买价），并在此基础上增加（减少）0.1 元购买（卖出）。若市场上还没有挂单，则会询问开盘价。
AI 有 20% 的概率是机构投资者，80% 的概率是个人投资者（散户）；
若 AI 为机构投资者，则 AI 计划交易 10～20 万股，每次交易 2000～5000 股，每 10 个周期挂单一次；挂单 10 个周期后询问该单是否成交，如未成交再挂一单。
若 AI 为散户，则 AI 计划交易 5～11 万股，正常情况每次交易 100～400 股。每 1 个周期交易一次。挂单 1 个周期后询问该单是否成交，如未成交再挂一单。
当股票连续涨了三个周期或跌了三个周期时，买方或卖方散户将每次交易 200～900 股，原来计划卖出或买入的 AI 有 60% 的概率停止他们的行为。（可以看出，这样的设定使得 AI 的行为非常接近真实市场中「追涨杀跌」的行为。）当股价接近 40 元高点时，部分投资者将由于股价过高而改变交易方向。如一个买入股票的 AI，当它发现股价超过 40 元时，会选择暂时卖出，等股价低于 40 以后再买入。
AI 是买方或者卖方的概率都是随机的。
测试项目一：「二项堆」和「有缓冲的二项堆」的速度比较
若使用程序每秒生成 10000 个挂单并报入交易平台，样例程序中的速度计算如下：
有缓冲区的二项堆工作效率非常高，是没有缓冲区程序速度的近一千倍。
测试项目二：交易软件运行的正确性
该图为交易软件在有 60 个 AI 交易的过程中的运行截图。可以看出，AI 交易生成的分时线和交易量柱状图和真实股票市场中的图形十分近似。并且，在 60 个客户端登录时，本软件保持着较好的运行速度。极限情况下，在 2G 双核 CPU 的笔记本上单机同时运行客户端和服务器测试，程序可以高效保持连接 250 个客户端情况下的计算。
（编辑：陈岑）
作者 丁海韬