J. W. J. Williams

John William Joseph (Bill) Williams[1] (September[2][3] 1930 – 29 September 2012)[3][4] was a computer scientist best known for inventing heapsort and the binary heap data structure in 1963 while working for Elliot Bros. (London) Ltd.[5][6][7][8]

Personal life

He was born in England,[9] specifically in the district Chippenham in the county Wiltshire,[2] to William Henry Williams[4] and Mrs. Haines.[2] During the 1939 Register, he lived at 12 The Vicarage St Mary Street, Chippenham M.B., Wiltshire, England[10] with Joseph Haines (born 1871), Eva F Williams (born 1903), and William H Williams (born 1883).[11]

Eva Florence Haines (born in Chippenham) was the daughter of Joseph Haines and Florence Ellen Light (born circa 1884).[12][13][14] William H Williams (born 23 July 1883) and Eva Florence Haines (born 13 March 1903) were married on 29 January 1929 in Chippenham, Wiltshire, England.[12][15][16]

On 3 March 1962, John William Joseph Williams (mathematician,[9] age 31) married Ann[3][6] Zerny (nurse,[6] age 23) at Christ Church in Chorleywood Parish in Hertfordshire County.[4] They had children named Peter (Carey), Rob (Rick) and Richard (Charlotte), who had children named Rowan, Derek, Emmett, Reed, and Seth.[3]

In 1974, he moved to Ottawa, Ontario, Canada.[3][6][9] On 10 June 1994, he was living at 18 Banting Crescent, Kanata, Ontario, Canada K2K 1P4.[1] He volunteered for Kanata Theatre, helping construct sets, design lighting, and occasionally act on stage.[3]

On 29 September 2012, he died at age 82; on 6 October, he had a Celebration of Life at the Ron Maslin Playhouse, requesting donations in his memory to be given to Kanata Theatre and Ottawa Heart Institute.[3]

Career

In 1952, he received a B.Sc. in mathematics from King's College, University of London.[9]

In England, he worked as a programmer for Elliot Automation,[9] formerly Elliot Brothers (London) Limited, where he invented heapsort and used it to create the event-driven Elliott Simulator Package (ESP) with the help of C. A. R. (Tony) Hoare.[5][6][17] He also worked for English Electric and GEC.[9] He worked with Donald E. Knuth to develop a two-heap data structure that they called a "priority deque", published as an exercise in The Art of Computer Programming in 1973.[18][19]

After moving to Canada in 1974, he worked for Bell-Northern Research Ltd., Ottawa (BNR) and Northern Telecom (Nortel) until retiring in 1995.[3][6] At BNR, he worked on various software and hardware systems such as the DMS-100 digital telephone switch, publishing a paper about their software in June 1982.[9] On 10 March 1988, Northern Telecom (retroactively initially Bell-Northern Research[20]) filed a US, and subsequently international, patent for a "Digital Key Telephone System", listing him as an inventor.[21][22][23][1] In 1992, he told Andre Vellino of Nortel Networks that "Design is the art of defining a system to meet a set of constraints".[24]

References

1. Patent CA 1334303, Documents, PCT Correspondence on 1994-07-21, p. 5. (objectName=A1001001A20A23A93837H72760)
2. "Record Transcription: England & Wales Births 1837-2006". Findmypast. brightsolid online publishing ltd. Retrieved 2 November 2023. First name(s): John W J, Last name: Williams, Birth quarter: 4, Birth year: 1930, Mother's maiden name: Haines, District: Chippenham, County: Wiltshire
3. "J.W.J. WILLIAMS Obituary (2012)". Ottawa Citizen. 4 October 2012. Retrieved 20 September 2023 – via Legacy Remembers.
4. Marriage certificate for John William Joseph Williams and Ann Zerny, 3 March 1962.
   GRO Reference Information: Year=1962, Qtr=M, Vol=04B, Page=686 (from https://www.familysearch.org/ark:/61903/1:1:QV64-HY9Y)
   Text of document (ordered from https://www.gro.gov.uk/):

   CERTIFIED COPY OF AN ENTRY OF MARRIAGE

   
   Given at the GENERAL REGISTER OFFICE

   1962. Marriage solemnized at Christ Church in the Parish of Chorleywood in the County of Herts

   No: 61
   When married: March 3rd, 1962
   Name and surname: John William Joseph Williams / Ann Zerny
   Age: 31 / 23
   Condition: Bachelor / Spinster
   Bank or profession: Mathematician / Staff Nurse
   Residence at the time of marriage: 1, Windham Cottage, Wild Hill, Hatfield / <redacted as per WP:BLPPRIVACY>
   Father's name and surname: William Henry Williams (Deceased) / <redacted as per WP:BLPNAME>
   Rank or profession of father: <not specified> / <redacted as per WP:BLPPRIVACY>

   Married in the Parish Church according to the rites and ceremonies of the Established Church after Banns by me, John H. G. Gilliet, Vicar.
   This marriage was solemnized between us, } John William Joseph Williams / Ann Zerny } in the presence of us, { <redacted as per WP:BLPNAME>.

   CERTIFIED to be a true copy of an entry in the certified copy of a register of Marriages in the Registration District of Watford
   Given at the General Register Office, under the Seal of the said Office, the 5th day of October 2023
   MXJ 769947
   

   2340156 04/23 APS/A1SP

5. Williams, J. W. J. (1 June 1964) [Received 1 October 1963, revised 15 February 1964.]. Forsythe, G. E. (ed.). "Algorithm 232: Heapsort". Algorithms. Communications of the ACM. 7 (6): 347–348. doi:10.1145/512274.512284. ISSN 0001-0782 – via ACM Digital Library. Elliott Bros. (London) Ltd., Borehamwood, Herts, England
6. Hantman, Nancy T. (December 1997). "And the winners are ... Spectrum's Second Quilt Block Contest". IEEE Spectrum. 34 (12): 49. doi:10.1109/MSPEC.1997.642968. eISSN 1939-9340. ISSN 0018-9235 – via IEEE Xplore. COMPUTERS/FABRIC: Heapsort by J. W. J. (Bill) and Ann Williams, Kanata, Ont., Canada.
7. Brodal, Gerth Stølting; Pinotti, M. Cristina (1998). "Comparator networks for binary heap construction". In Arnborg, Stefan; Ivansson, Lars (eds.). Algorithm Theory — SWAT'98. Lecture Notes in Computer Science. Vol. 1432. Berlin, Heidelberg: Springer. pp. 158–168. doi:10.1007/BFb0054364. hdl:11858/00-001M-0000-0014-9A0B-B. ISBN 978-3-540-69106-8.
8. Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (19 May 2012). "Strict fibonacci heaps". Proceedings of the forty-fourth annual ACM symposium on Theory of computing. STOC '12. New York, NY, USA: Association for Computing Machinery. pp. 1177–1184. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5. S2CID 3107885.
9. Penney, Brian K.; Williams, J. W. J. (June 1982) [Manuscript received 21 July 1981; revised 17 December 1981.]. "The Software Architecture for a Large Telephone Switch". IEEE Transactions on Communications. COM-30 (6): 1369–1378. doi:10.1109/TCOM.1982.1095594. eISSN 1558-0857. ISSN 0090-6778 – via IEEE Xplore.
10. "Search Results for 1939 Register: first name = "J.w.j." (incl. variants), last name = "Williams" (no variants), birth year = 1930 (±0)". Findmypast. Retrieved 2 November 2023.
11. "Search Results for 1939 Register: borough/district = "Chippenham M.b.", street = "St Mary"". Findmypast. Retrieved 2 November 2023.
12. "Eva Florence Haines (1903–Deceased), William H Williams (1883–Deceased) • Landscape View • Family Tree". FamilySearch. Retrieved 2 November 2023.
13. "England and Wales Census, 1911," database, FamilySearch (https://familysearch.org/ark:/61903/1:1:X72L-42Y : 21 July 2019), Eva Florence Haines in household of Joseph Haines, Chippenham with Tytherton Lucas, Wiltshire, England, United Kingdom; from "1911 England and Wales census," database and images, findmypast (http://www.findmypast.com : n.d.); citing PRO RG 14, The National Archives of the UK, Kew, Surrey.
14. "Record Transcription: England & Wales Births 1837-2006: Eva Florence Haines in 1903". Findmypast. brightsolid online publishing ltd. Retrieved 2 November 2023.
15. "Record Transcription: England & Wales Marriages 1837-2005: Eva F Haines in 1929". Findmypast. brightsolid online publishing ltd. Retrieved 2 November 2023.
16. "Record Transcription: England & Wales Marriages 1837-2005: William H Williams in 1929". Findmypast. brightsolid online publishing ltd. Retrieved 2 November 2023.
17. Williams, J. W. J. (1 January 1964). "E.S.P. The Elliott Simulator Package". The Computer Journal. 6 (4). The British Computer Society: 328–331. doi:10.1093/comjnl/6.4.328 – via Oxford Academic, Oxford University Press.
18. Sepesi, Greg (14 June 2007). "Dualheap Selection Algorithm: Efficient, Inherently Parallel and Somewhat Mysterious". arXiv:0706.2155v1 [cs.DS].
19. Knuth, Donald Ervin (1973). "5.2.3 Sorting by Selection, Exercise 31". The Art of Computer Programming: Sorting and searching. Vol. 3 (1st ed.). Addison-Wesley Publishing Company. p. 159. ISBN 978-0-201-03803-3.
20. "Patent assignment 004918/0852". Patent Assignment Search. United States Patent and Trademark Office. 20 July 1988 [Execution date: 30 May 1988]. Retrieved 2 November 2023.
21. US 4893310A, Robertson, David J.; Maginley, Ronald J. & Chapman, Alan S. J. et al., "Digital key telephone system", issued 1990-01-09, assigned to Northern Telecom Limited, Montreal, Canada 
22. US 5136585A, Nizamuddin, Nadir; Chapman, Alan S. J. & Williams, John W. J. et al., "Digital key telephone system", issued 1992-08-04, assigned to Northern Telecom Limited, Montreal, Canada 
23. Patent CA 1334303, Documents, Office Letter on 1989-08-03. (objectName=A1001001A20A23A93406H72702)
24. Vellino, Andre (October 2001). "Toward a Methodology of Rational System Design". ResearchGate. pp. 2, 13. Retrieved 2 November 2023.
    
    "Essay Books". Philosophia Mathematica. 10 (2): 252-253.
    states that this has been published in
    Woods, John; Brown, Bryson, eds. (2001). New Studies in Exact Philosophy: Logic, Mathematics and Science. 1999 Conference of the Society of Exact Philosophy. Oxford: Hermes Science Publishing. pp. 307–320. ISBN 1-903398-18-5.